方格填色

发布时间: 2018年6月14日 17:53   最后更新: 2018年6月14日 17:55   时间限制: 2000ms   内存限制: 256M

给一个$m \times n$的方格,每个格子可以是黑色或者白色。要求左右相邻两格不能同为白色且相邻两列不能全为黑色。

求满足条件的方案数。

第一行有一个整数$T$,表示测试数据的组数。
对于每组测试数据,输入两个整数$m, n$。
$T \le 10$
$1 \le m \le 5$
$1 \le n \le 10 ^ {18}$

对于每组测试数据,在一行内输出答案,由于这个数可能很大,请将其对$10^9 + 7$取模。

复制
5
1 2
2 4
3 6
4 8
5 10
2
38
6314
7179538
674119951

dp

ACM集训队暑期集训热身赛