Pierre 以制作马卡龙而闻名。他制作圆形马卡龙，存放在 $1 \times 1$ 的方形盒子里；以及椭圆形马卡龙，存放在 $1 \times 2$（或旋转后为 $2 \times 1$）的矩形盒子里。为了准备自助餐，Pierre 希望用这两种马卡龙铺满一个 $N \times M$ 的矩形桌面，这意味着桌面必须完全填满，不能留有空隙。桌子的宽度 $N$ 很小，方便客人拿取马卡龙；而桌子的长度 $M$ 很大，以容纳大量的客人。为了保持桌面的美观，马卡龙的摆放方向必须始终与桌子的边缘对齐。

Pierre 想知道有多少种铺满桌面的方法。你能帮帮他吗？

输入格式

输入包含以下整数： 第一行是一个整数 $N$； 第二行是一个整数 $M$。

数据范围

输入满足 $1 \leqslant N \leqslant 8$ 且 $1 \leqslant M \leqslant 10^{18}$。

输出格式

输出一行，表示铺满桌面的总方案数，结果对 $10^9$ 取模。

样例

样例输入 1

2
2

样例输出 1

7

样例输入 2

2
4

样例输出 2

71