你手上有一份拼图需要完成。
具体地说，有 个空格子，初始状态下这些空格子上没有东西。你手上有两种大小为 个格子的零片（如下图所示，实际上也就只有这两种），各有无数个，你可以将它们任意旋转后拼到图里。
请问一共有多少种方案能使你填满所有格子。
一行一个正整数 。
一行一个正整数代表答案。由于答案可能很大，你需要对 取模。
2
3
10000
18474502
对于 的数据，
