首页 > 试题广场 >

方格填色

[编程题]方格填色
给一个m x n的方格,Applese想要给方格填上颜色,每个格子可以是黑色或者白色。他要求左右相邻两格不能同为白色且相邻两列不能全为黑色。

求满足条件的方案数。

输入描述:
输入两个整数m, n。(1 ≤ m ≤ 5, 1 ≤ n ≤ 1018)。


输出描述:
输出答案对109 + 7取模的结果。
示例1

输入

3 1

输出

8
示例2

输入

3 5

输出

1640
示例3

输入

5 5

输出

351032

这道题你会答吗?花几分钟告诉大家答案吧!