我们讲解了 $2 \times N$、$3 \times N$ 骨牌覆盖的问题，并且引入了两种不同的递推方法。这一次我们再加强题目，对于给定的 $K$ 和 $N$，我们需要求出用 $1 \times 2$ 骨牌覆盖 $K \times N$ 棋盘的方案数。

输入格式

第一行：两个整数 $K, N$，表示棋盘高度为 $K$，长度为 $N$。

输出格式

第一行：一个整数，表示覆盖方案数对 12357 取模的结果。

样例

样例输入 1

2 62247088

样例输出 1

1399

数据范围

• $20\%$ 的数据，$K = 2$
• $20\%$ 的数据，$K = 3$
• $20\%$ 的数据，$K = 4$
• $20\%$ 的数据，$K = 5$
• $10\%$ 的数据，$K = 6$
• $10\%$ 的数据，$K = 7$
• $100\%$ 的数据，$n$ 不超过 $10^9$