简单题目系列之砌墙

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

用 1×1×1, 1× 2×1以及2×1×1的三种木块.
搭建高长宽分别为K × 2^N × 1的墙(其中,0<=N<=1024,1<=K<=4)
有多少种方案,输出结果
对1000000007取模。

Input

 首先输入一个t,代表有t组(t = 10)
每组输入两个数n,k

Output

 输出t组。每行一个数代表结果

Sample Input

1
1 2

Sample Output

7

Hint

 

Source

zp