题目描述

给一个$m × n$的方格，Applese想要给方格填上颜色，每个格子可以是黑色或者白色。他要求左右相邻两格不能同为白色且相邻两列不能全为黑色。

求满足条件的方案数。

输入

输入两个整数$m, n$。$(1 ≤ m ≤ 5, 1 ≤ n ≤ 10^{18})$。

输出

输出答案对$10^9 + 7$取模的结果。

样例

3 1

8

3 5

1640

5 5

351032