【问题描述】

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

【输入数据】

输入数据仅一个自然数N(N≤10^6)。

【输出数据】

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

【输入样例】 domino.in

5

【输出样例】 domino.out

0000000000000000000000000
0000000000000000000000000
0000000000000000000000000
0000000000000000000000008