Description

有N块1×2大小的骨牌需要放入一个2×N的牌盒中，请问共有多少种放法（输出总放法数的最后100位即可）。

Input

输入数据仅一个自然数N（N≤10^4）。

Output

输出数据共4行，每行25位，共100位。表示总放法数的最后100位。不满100位时高位用0补足。

Sample

Input

5

Output

0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000008