问题描述：

求所有可以只用1和00拼成的长度为N的二进制数的个数除以15746的余数。 比如，当N=4时，有5个可能的二进制数：0011，0000，1001，1100，1111。

输入格式：一行，一个正整数N（最大1000000）。

输出格式：输出所有可以只用1和00拼成的长度为N的二进制数的个数除以15746的余数。

输入样例：

4

输出样例：

5