问题描述：

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

比如，当N=4时，有5个可能的二进制数：0011，0000，1001，1100，1111。

输入格式：

一行，一个正整数N（最大1000000）。

输出格式：

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

4

5