You have an infinite number of 4 types of lego blocks of sizes given as (depth x height x width):

d	h	w
1	1	1
1	1	2
1	1	3
1	1	4

Using these blocks, you want to make a wall of height $n$ and width $m$. Features of the wall are: 

- The wall should not have any holes in it. 

- The wall you build should be one solid structure, so there should not be a straight vertical break across all rows of bricks. 

- The bricks must be laid horizontally.   

How many ways can the wall be built?

Example  

$n=2$ 

$m=3$  

The height is $2$ and the width is $3$.  Here are some configurations:  

These are not all of the valid permutations.  There are $\mbox{9}$ valid permutations in all.  

Function Description  

Complete the legoBlocks function in the editor below.  

legoBlocks has the following parameter(s):

int n: the height of the wall  
int m: the width of the wall   

Returns 

- int: the number of valid wall formations modulo $(10^9+7)$  

Input Format

The first line contains the number of test cases $\boldsymbol{\boldsymbol{t}}$.  

Each of the next $\boldsymbol{\boldsymbol{t}}$ lines contains two space-separated integers $n$ and $m$.  

Constraints

$1\leq t\leq100$ 

$1\leq n,m\leq1000$  

Sample Input
STDIN   Function
-----   --------
4       t = 4
2 2     n = 2, m = 2
3 2     n = 3, m = 2
2 3     n = 2, m = 3
4 4     n = 4, m = 4

Sample Output
3  
7  
9  
3375

Explanation

For the first case, we can have:  

$3\:\:\:\text{mod}\:(10^9+7)=3$  

For the second case, each row of the wall can contain either two blocks of width 1, or one block of width 2. However, the wall where all rows contain two blocks of width 1 is not a solid one as it can be divided vertically. Thus, the number of ways is $2\times2\times2-1=7$ and $7\:\:\:\text{mod}\:(10^9+7)=7$.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
MAX = 1000000007

def calcLevels(levels):
	N = len(levels)
	M = len(levels[1])
	levels[1][0] = 1
	p = 1
	while p < M:
		i = 1
		while i <= 4 and p - i >= 0:
			levels[1][p] = (levels[1][p] + levels[1][p - i]) % MAX
			i += 1
		p += 1
	n = 2
	while n < N:
		p = 1
		while p < M:
			levels[n][p] = levels[n - 1][p] * levels[1][p] % MAX
			p += 1
		n += 1

def getDP(dp, levels, N, M):
	if dp[N][M] != 0:
		return dp[N][M]
	curTmp = levels[N][M]
	p = 1
	while p < M:
		if dp[N][p] == 0:
			curTmpLow = levels[N][p]
			q = 1
			while q < p:
				curTmpLow = (curTmpLow - dp[N][q] * levels[N][p - q]) % MAX
				q += 1
			dp[N][p] = curTmpLow
		curTmp = (curTmp - dp[N][p] * levels[N][M - p]) % MAX
		p += 1
	dp[N][M] = curTmp
	return dp[N][M]
T = int(input())
inputs = [[0, 0] for i in range(T)]
(maxN, maxM) = (0, 0)
p = 0
while p < T:
	(N, M) = [int(i) for i in input().split(' ')]
	if N > maxN:
		maxN = N
	if M > maxM:
		maxM = M
	inputs[p][:] = (N, M)
	p += 1
levels = [[0 for i in range(maxM + 1)] for j in range(maxN + 1)]
dp = [[0 for i in range(maxM + 1)] for j in range(maxN + 1)]
calcLevels(levels)
p = 0
while p <= maxN:
	dp[p][1] = 1
	p += 1
p = 1
while p <= maxM:
	dp[1][p] = levels[1][p]
	p += 1
p = 0
while p < T:
	(N, M) = inputs[p]
	if N == 1 and M >= 1 and (M <= 4):
		print(1)
	elif N == 1:
		print(0)
	else:
		print(getDP(dp, levels, N, M))
	p += 1


def go(n, m):
	M = 1000000007
	f = [1, 1, 2, 4]
	for i in range(4, m + 1):
		f.append(sum(f[-4:]))
	F = [0, 1]
	for i in range(2, m + 1):
		v = f[i] = pow(f[i], n, M)
		for j in range(1, i):
			v -= F[j] * f[i - j]
		F.append(v % M)
	return F[-1]
for t in range(int(input())):
	print(go(*map(int, input().split())))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


A = 1000000007
inp = []
for _ in range(int(input())):
	[n, m] = [int(x) for x in input().split()]
	inp.append((n, m))
m_max = max([a[1] for a in inp])
r = [1, 2, 4, 8]
for i in range(4, m_max):
	r.append(sum(r[i - 4:i]) % A)
for (a, b) in inp:
	t = [1]
	s = [pow(x, a, A) for x in r[:b]]
	for j in range(1, b):
		t.append((s[j] - sum([t[k] * s[j - k - 1] % A for k in range(j)])) % A)
	print(t[-1])


m = 1000000007
dp1 = [1, 1, 2, 4]
for i in range(4, 1001):
	dp1.append((dp1[-1] + dp1[-2] + dp1[-3] + dp1[-4]) % m)

def f(h, w):
	dp2 = []
	dp3 = [pow(dp1[i], h, m) for i in range(w + 1)]
	for i in range(w + 1):
		tmp = dp3[i]
		for j in range(1, i):
			tmp = (tmp - dp2[j] * dp3[i - j]) % m
		dp2.append(tmp)
	return dp2[-1]
for e in range(int(input())):
	print(f(*list(map(int, input().split()))))


modc = 1000000007
maxn = 1000 + 5
a = {}
a[1, 1] = 1
a[1, 2] = 2
a[1, 3] = 4
a[1, 4] = 8
for i in range(5, maxn):
	a[1, i] = (a[1, i - 1] + a[1, i - 2] + a[1, i - 3] + a[1, i - 4]) % modc
for h in range(2, maxn):
	for w in range(1, maxn):
		(p, d) = (a[h // 2, w], a[1, w] if h % 2 == 1 else 1)
		a[h, w] = p * p * d % modc
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = [0] * maxn
	s[1] = 1
	for i in range(2, m + 1):
		w = sum((s[j] * a[n, i - j] % modc for j in range(1, i))) % modc
		s[i] = (a[n, i] - w + modc) % modc
	print(s[m])


modulo = 1000000007
g = [0 for x in range(1000)]
g[0:4] = [1, 2, 4, 8]
for i in range(4, 1000):
	g[i] = (g[i - 1] + g[i - 2] + g[i - 3] + g[i - 4]) % modulo
T = int(input())
for i in range(T):
	[N, M] = [int(x) for x in input().split()]
	unconst = [0 for x in range(M)]
	const = [0 for x in range(M)]
	for j in range(M):
		unconst[j] = pow(g[j], N, modulo)
	for j in range(M):
		const[j] = unconst[j] % modulo
		for k in range(j):
			const[j] = (const[j] - unconst[k] * const[j - k - 1]) % modulo
	print(const[M - 1])


MOD = 10 ** 9 + 7

def main(MOD=MOD, rowtbl=[1]):
	ncases = int(input())
	for case in range(ncases):
		(rows, cols) = map(int, input().split())
		while len(rowtbl) <= cols:
			rowtbl.append(sum(rowtbl[-4:]) % MOD)
		walltbl = [pow(possrows, rows, MOD) for possrows in rowtbl]
		solidtbl = []
		for i in range(cols + 1):
			solidtbl.append((walltbl[i] - sum((solidtbl[j] * walltbl[i - j] for j in range(1, i)))) % MOD)
		print(solidtbl[-1])
main()


mod = 1000000007
max_w = 1000

def pow(a, b):
	a %= mod
	result = 1
	while b > 0:
		if b & 1:
			result = result * a % mod
		a = a * a % mod
		b = b >> 1
	return result
n_rows = [0] * (max_w + 1)
n_rows[0] = 1
n_rows[1] = 1
n_rows[2] = 2
n_rows[3] = 4
n_rows[4] = 8
for i in range(5, max_w + 1):
	n_rows[i] = (n_rows[i - 1] + n_rows[i - 2] + n_rows[i - 3] + n_rows[i - 4]) % mod
T = int(input())
for _ in range(T):
	(h, w) = [int(i) for i in input().split()]
	n_grids = [pow(n, h) for n in n_rows]
	n_no_splits = [1] * (w + 1)
	for i in range(2, w + 1):
		s = 0
		for j in range(1, i):
			s = (s + n_no_splits[j] * n_grids[i - j]) % mod
		n_no_splits[i] = (n_grids[i] - s + mod) % mod
	print(n_no_splits[-1])


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


mod = 1000000007
T = int(input())
for case in range(T):
	(N, M) = map(int, input().rstrip().split())

	def solve():
		if N == 1:
			return 1 if M < 5 else 0
		row_comb = [0] * (M + 1)
		row_comb[0] = 1
		for i in range(len(row_comb)):
			for coin in [1, 2, 3, 4]:
				if i - coin >= 0:
					row_comb[i] += row_comb[i - coin]
		total_comb = [pow(i, N, mod) for i in row_comb]
		unstable_comb = [0] * (M + 1)

		def stable_comb(k):
			return total_comb[k] - unstable_comb[k]
		for i in range(2, M + 1):
			for j in range(1, i):
				unstable_comb[i] += total_comb[j] * stable_comb(i - j)
			unstable_comb[i] %= mod
		return stable_comb(M) % mod
	print(solve())


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


def lego_blocks(N, M):
	S = [0 for _ in range(M)]
	P = [0 for _ in range(M)]
	Q = [0 for _ in range(M)]
	for i in range(M):
		Q[i] += pow(2, i) if i < 4 else Q[i - 1] + Q[i - 2] + Q[i - 3] + Q[i - 4]
		Q[i] %= 1000000007
	for i in range(M):
		P[i] = pow(Q[i], N, 1000000007)
	for i in range(M):
		S[i] = P[i]
		for j in range(1, i + 1):
			S[i] -= P[j - 1] * S[i - j]
			S[i] %= 1000000007
	return S[M - 1] % 1000000007

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = [int(i) for i in input().split()]
		print(lego_blocks(N, M))
main()


tc = int(input())
mod = 1000000007
while tc:
	tc -= 1
	(N, M) = input().split()
	(N, M) = (int(N), int(M))
	d = {-3: 0, -2: 0, -1: 0, 0: 1, 1: 1}
	for i in range(2, M + 1):
		d[i] = (d[i - 1] + d[i - 2] + d[i - 3] + d[i - 4]) % mod
	D = {1: 1}
	for i in range(2, M + 1):
		d[i] = pow(d[i], N, mod)
		ans = d[i]
		for j in range(1, i):
			ans -= d[i - j] * D[j]
		ans = ans % mod
		if ans < 0:
			ans = mod - ans
		D[i] = ans
	print(D[M])


def modPower(value, toPower, toMod):
	powered = value
	for i in range(1, toPower):
		powered *= value
		if powered > 1000000007:
			powered %= toMod
	return powered % toMod

def LegoSum(H, W):
	A = [0] * (W + 1)
	L = [0] * (W + 1)
	A[0] = 1
	for i in range(1, W + 1):
		for j in range(1, 5):
			if i >= j:
				A[i] += A[i - j]
		if A[i] > 1000000007:
			A[i] = A[i] % 1000000007
	for i in range(1, W + 1):
		A[i] = modPower(A[i], H, 1000000007)
	L[1] = 1
	for w in range(2, W + 1):
		toDel = 0
		for i in range(1, w):
			toDel += L[i] * A[w - i]
		L[w] = (A[w] - toDel) % 1000000007
	return L[W] % 1000000007
T = int(input())
for _ in range(T):
	(H, W) = tuple(map(int, input().split()))
	print(LegoSum(H, W))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
from sys import stdin
from array import array as ar
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)
if home:
	filou = lolPath + '\\Lego00.txt'
	filin = 'D:\\ZeDaddy\\Documents\\Hack\\combinatorics\\JourneyOu03.txt'
	from mesures import ch
else:
	filou = None
modo = 10 ** 9 + 7

def ligNRecur(M):
	r = [1, 1] + [0] * max(M - 1, 4)
	r[2] = sum(r)
	r[3] = sum(r)
	r[4] = sum(r)
	(a, b, c, d, e) = (1, 1, 2, 4, 8)
	r[0:4] = (a, b, c, d, e)
	for m in range(5, M + 1, 5):
		a = (2 * e - a) % modo
		b = (2 * a - b) % modo
		c = (2 * b - c) % modo
		d = (2 * c - d) % modo
		e = (2 * d - e) % modo
		r[m:m + 5] = (a, b, c, d, e)
	return r[:M + 1]

def rectNRecur(M):
	jointifs = {}
	jointifs[1] = 1
	jointifs[0] = 1
	for MM in range(2, M + 1):
		jointifs[MM] = fulls[MM] - sum((jointifs[m] * fulls[MM - m] for m in range(1, MM))) % modo
		if jointifs[MM] < 0:
			jointifs[MM] += modo
	return jointifs[M]
if home:
	from mesures import ch, prof
rd = open(filou) if filou else stdin
Li = [list(map(int, rd.readline().strip().split())) for _ in range(int(rd.readline().strip()))]
(maxn, maxm) = (max((v[0] for v in Li)), max((v[1] for v in Li)))
ligs = ligNRecur(maxm)
for (n, m) in Li:
	fulls = [pow(lig, n, modo) for lig in ligs]
	print(rectNRecur(m))


mod = 1000000007
lim = 1000
A = [0] * (lim + 1)
for i in range(1, 5):
	A[i] = sum(A[:i]) + 1
for i in range(5, lim + 1):
	A[i] = sum(A[i - 4:i]) % mod
for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	H = [0] * (m + 1)
	for i in range(1, m + 1):
		H[i] = pow(A[i], n, mod)
	S = [0] * (m + 1)
	for i in range(1, m + 1):
		S[i] = (H[i] - sum([S[j] * H[i - j] for j in range(1, i)]) % mod + mod) % mod
	print(S[m])


MOD = int(1000000000.0 + 7)
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	ways = [0] * (M + 4)
	ways[0] = 1
	for i in range(M):
		for j in range(1, 5):
			ways[i + j] = (ways[i + j] + ways[i]) % MOD
	res = [0] * (M + 1)
	resbad = [0] * (M + 1)
	resgood = [0] * (M + 1)
	resgood[1] = 1
	resbad[1] = 0
	res[1] = 1
	for i in range(2, M + 1):
		res[i] = pow(ways[i], N, MOD)
		for j in range(1, i):
			resbad[i] += resgood[j] * res[i - j] % MOD
		resgood[i] = (res[i] - resbad[i] % MOD + MOD) % MOD
	print(resgood[M])


maxb = 4
maxl = 1000
M = 10 ** 9 + 7
arrange = [1]
for i in range(1, maxl + 1):
	ways = 0
	for j in range(1, maxb + 1):
		if i - j >= 0:
			ways += arrange[i - j]
	arrange.append(ways % M)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	valid = [1]
	total = [0]
	for i in range(1, m + 1):
		total.append(pow(arrange[i], n, M))
	for i in range(1, m + 1):
		invalid = 0
		for j in range(1, i):
			invalid += valid[j] * total[i - j] % M
		valid.append((total[i] - invalid) % M)
	print(valid[m])


m = 1000000007
raw = [0] * 1001
raw[1] = 1
raw[2] = 2
raw[3] = 4
raw[4] = 8
for i in range(5, 1001):
	raw[i] = (raw[i - 1] + raw[i - 2] + raw[i - 3] + raw[i - 4]) % m

def modexp(b, e):
	rv = 1
	bb = b
	ee = e
	while ee > 0:
		if ee & 1 == 1:
			rv = rv * bb % m
		bb = bb * bb % m
		ee >>= 1
	return rv
num_probs = int(input())
for prob in range(num_probs):
	(h, w) = (int(x) for x in input().split())
	base = [modexp(raw[i], h) for i in range(w + 1)]
	count = [0] * (w + 1)
	for i in range(1, w + 1):
		count[i] = base[i]
		for j in range(1, i):
			count[i] = (count[i] - count[j] * base[i - j]) % m
	print(count[w])


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_comb = [1, 1, 2, 4]
	while len(row_comb) <= M:
		row_comb.append(sum(row_comb[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_comb]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


K = 1000000007
MAXM = 1001
T = int(input().strip())
W = [-1] * MAXM
for (m, c) in enumerate((0, 1, 2, 4, 8, 15, 29, 56, 108)):
	W[m] = c
for m in range(9, MAXM):
	W[m] = ((W[m - 1] << 1) - W[m - 5]) % K
for t in range(T):
	(N, M) = map(int, input().strip().split())
	if N == 1:
		print(1 if 0 < M < 5 else 0)
		continue
	WNM = [-1] * (M + 1)
	WNM[0] = 0
	WNM[1] = 1
	POW = [-1] * (M + 1)
	for m in range(M + 1):
		POW[m] = pow(W[m], N, K)
	for m in range(2, M + 1):
		notgood = 0
		for i in range(1, m):
			notgood += WNM[i] * POW[m - i] % K
		res = POW[m] - notgood % K
		if res < 0:
			res += K
		WNM[m] = res
	print(WNM[M])


MOD = 1000000007

def ways_to_build_solid_block(N, M, block_sizes):
	M_TO_SOLVE = M
	M = max(M, 4)
	total = [0] * (M + 1)
	for block_size in block_sizes:
		total[block_size] = 1
	for i in range(1, M + 1):
		sum_total_i = 0
		for block_size in block_sizes:
			if i - block_size >= 0:
				sum_total_i += total[i - block_size]
		total[i] = total[i] + sum_total_i
		total[i] = total[i] % MOD
	for i in range(1, M + 1):
		total[i] = pow(total[i], N, MOD)
	solid = [0] * (M + 1)
	separable = [0] * (M + 1)
	solid[1] = 1
	separable[1] = 0
	for m in range(2, M + 1):
		sum_separable_m = 0
		for separate_index in range(1, m):
			sum_separable_m += total[separate_index] * solid[m - separate_index]
			sum_separable_m = sum_separable_m % MOD
		separable[m] = sum_separable_m
		solid[m] = total[m] - separable[m]
		solid[m] = solid[m] % MOD
	return solid[M_TO_SOLVE]
block_sizes = [1, 2, 3, 4]
t = int(input())
for _ in range(t):
	(N, M) = map(int, input().split())
	answer = ways_to_build_solid_block(N, M, block_sizes)
	print(answer)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


def expand_row_config_arr(width):
	curr_len = len(row_config_arr)
	while curr_len <= width:
		a = row_config_arr[-1]
		b = row_config_arr[-2]
		c = row_config_arr[-3]
		d = row_config_arr[-4]
		next_num = (a + b + c + d) % 1000000007
		row_config_arr.append(next_num)
		curr_len += 1
num_tests = int(input())
row_config_arr = [0, 1, 2, 4, 8]
for i in range(num_tests):
	N_M = input().split()
	N = int(N_M[0])
	M = int(N_M[1])
	if len(row_config_arr) <= M:
		expand_row_config_arr(M)
	T = [0, 1]
	S = [0, 1]
	U = [0, 0]
	for k in range(2, M + 1):
		T.append(pow(row_config_arr[k], N, 1000000007))
		U.append(0)
		for l in range(1, k):
			U[k] = U[k] + S[l] * T[k - l]
		U[k] = U[k] % 1000000007
		S.append((T[k] - U[k]) % 1000000007)
	print(S[-1])


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


import sys
MOD = 1000000007
bufArr = [1, 2, 4, 8]
powArr = [1]
solArr = [1]

def makeBufArr(width):
	for i in range(len(bufArr), width):
		bufArr.append((bufArr[i - 1] + bufArr[i - 2] + bufArr[i - 3] + bufArr[i - 4]) % MOD)

def makePowArr(height, width):
	for i in range(1, width):
		powArr.append(pow(bufArr[i], height, MOD))

def getSum(width):
	sum = 0
	for i in range(width):
		sum = (sum + powArr[i] * solArr[width - i - 1]) % MOD
	return sum

def getSolid(width):
	for i in range(1, width):
		solArr.append(powArr[i] - getSum(i) % MOD)
	return solArr[width - 1]
n = int(input().strip())
for q in range(n):
	(h, w) = input().strip().split(' ')
	(h, w) = [int(h), int(w)]
	if w == 1:
		print(1)
		continue
	if h == 1 and w <= 4:
		print(1)
		continue
	if h == 1 and w > 4:
		print(0)
		continue
	powArr = [1]
	solArr = [1]
	makeBufArr(w)
	makePowArr(h, w)
	print((getSolid(w) + MOD) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


t = int(input())
inps = []
(max_n, max_m) = (0, 0)
M = int(1000000000.0 + 7)
rows = []
cols = []
for test in range(t):
	(n, m) = [int(x) for x in input().split()]
	(max_n, max_m) = (max(max_n, n), max(max_m, m))
	inps.append((n, m))
	if not n in rows:
		rows.append(n)
		cols.append(m)
	z = rows.index(n)
	cols[z] = max(m, cols[z])
a = [[0] * (max_m + 1) for i in range(max_n + 1)]
dp = [[0] * (max_m + 1) for i in range(max_n + 1)]
for col in range(max_m + 1):
	a[0][col] = 1
for row in range(max_n + 1):
	a[row][0] = 1
for col in range(1, max_m + 1):
	a[1][col] = a[1][col - 1]
	if col - 2 > -1:
		a[1][col] += a[1][col - 2] % M
	if col - 3 > -1:
		a[1][col] += a[1][col - 3] % M
	if col - 4 > -1:
		a[1][col] += a[1][col - 4] % M
	a[1][col] %= M
for row in range(2, max_n + 1):
	for col in range(1, max_m + 1):
		a[row][col] = a[row - 1][col] * a[1][col] % M
for col in range(max_m + 1):
	dp[0][col] = 1
for row in range(max_n + 1):
	dp[row][0] = 1
for i in range(len(rows)):
	row = rows[i]
	for col in range(cols[i] + 1):
		dp[row][col] = a[row][col]
		for cut in range(1, col):
			dp[row][col] -= dp[row][cut] * a[row][col - cut]
		dp[row][col] %= M
for test in range(t):
	(n_, m_) = inps[test]
	print(dp[n_][m_] % M)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


memos = dict({0: 1, -1: 0, -2: 0, -3: 0})

def calc_one_high_wall(width):
	if width in memos:
		return memos[width]
	ans = sum((calc_one_high_wall(x) for x in range(width - 4, width))) % 1000000007
	memos[width] = ans
	return ans
one_high_wall = [calc_one_high_wall(x) for x in range(1100)]
memos2 = dict()
for h in range(2000):
	memos2[1, h] = 1
pow_ohw = dict()

def solve(width, height):
	if (width, height) in memos2:
		return memos2[width, height]
	modval = 1000000007
	if (width, height) not in pow_ohw:
		for w in range(width + 1):
			pow_ohw[w, height] = pow(one_high_wall[w], height, modval)
	if width % 100 == 1:
		solve(width - 100, height)
	solve(width - 1, height)
	one_high = one_high_wall[width]
	all_combos = pow(one_high, height, modval)
	err = 0
	for w in range(1, width):
		err += pow_ohw[w, height] * memos2[width - w, height]
	err %= modval
	ans = (all_combos + modval - err) % modval
	memos2[width, height] = ans
	return ans
for _ in range(int(input())):
	(height, width) = [int(x) for x in input().split()]
	ans = solve(width, height)
	print(ans)


M = 1000000007

def powMod(num, power):
	(c, e) = (1, 0)
	while e < power:
		e += 1
		c = num * c % M
	return c

def solve(h, w):
	memo = [0, 1, 2, 4, 8]
	A = [0, 1, powMod(2, h), powMod(4, h), powMod(8, h)]
	for i in range(5, w + 1):
		memo.append((memo[i - 1] + memo[i - 2] + memo[i - 3] + memo[i - 4]) % M)
		A.append(powMod(memo[i], h))
	S = [0, 1]
	for i in range(2, w + 1):
		total = A[i]
		for j in range(1, i):
			total -= S[j] * A[i - j] % M
		S.append(total % M)
	return S[w]
T = int(input())
for i in range(T):
	(H, W) = input().split(' ')
	(H, W) = (int(H), int(W))
	print(solve(H, W))


from operator import mul
lines = dict()
lines[0] = 1
blocks = [1, 2, 3, 4]
ways = dict()
fulls = dict()
finals = dict()

def noLine(w):
	if w in lines:
		return lines[w]
	count = 0
	for b in blocks:
		if w >= b:
			count += noLine(w - b)
	count = count % 1000000007
	lines[w] = count
	return count

def noFull(h, w):
	idx = '{} {}'.format(h, w)
	if idx in fulls:
		print('fulls yeah! h = {}, w = {}'.format(h, w))
		return fulls[idx]
	count = noLine(w)
	result = pow(count, h, 1000000007)
	fulls[idx] = result
	return result

def noWay(h, w):
	if w == 1:
		return 0
	idx = '{} {}'.format(h, w)
	if idx in ways:
		print('ways yeah! h = {}, w = {}'.format(h, w))
		return ways[idx]
	count = 0
	for i in range(1, w):
		count1 = noFinal(h, i)
		count2 = noFull(h, w - i)
		tmp = count1 * count2 % 1000000007
		count = (count + tmp) % 1000000007
	ways[idx] = count
	return count

def noFinal(h, w):
	idx = '{} {}'.format(h, w)
	if idx in finals:
		print('finals yeah! h = {}, w = {}'.format(h, w))
		return finals[idx]
	full = noFull(h, w)
	way = noWay(h, w)
	result = full - way
	if way > full:
		result += 1000000007
	finals[idx] = result
	return result
lines = [1]

def numLine(w):
	idxLines = len(lines)
	if idxLines > w:
		return
	for i in range(idxLines, w + 1):
		count = 0
		for b in blocks:
			if i >= b:
				count += lines[i - b]
		count = count % 1000000007
		lines.append(count)
	idxLines = w + 1
fulls = dict()

def numFull(h, w):
	idx = '{} {}'.format(h, w)
	if idx in fulls:
		return fulls[idx]
	numLine(w)
	count = lines[w]
	result = pow(count, h, 1000000007)
	fulls[idx] = result
	return result
finals = dict()

def numFinal(h, w):
	if h not in finals:
		tmp = dict()
		tmp['idx'] = 2
		tmp['count'] = [0, 1]
		tmp['c'] = [1]
		tmp['f'] = [1]
		finals[h] = tmp
	idx = finals[h]['idx']
	count = finals[h]['count']
	c = finals[h]['c']
	f = finals[h]['f']
	if idx > w:
		return
	for i in range(idx, w + 1):
		fulli = numFull(h, i)
		num = numFull(h, i)
		diag = sum(map(mul, f, c[::-1])) % 1000000007
		num -= diag
		if num < 0:
			num += 1000000007
		c.append(num)
		f.append(fulli)
		count.append(num)
	finals[h]['idx'] = w + 1
n = int(input())
for i in range(n):
	dim = [int(x) for x in input().split(' ')]
	h = dim[0]
	w = dim[1]
	numFinal(h, w)
	result = finals[h]['count'][w]
	print(result)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


P = 10 ** 9 + 7
MMAX = 1001

def main():
	L = [0] * MMAX
	L[0] = 1
	for i in range(1, MMAX):
		for j in range(1, min(4, i) + 1):
			L[i] = (L[i] + L[i - j]) % P
	T = int(input())
	for _ in range(T):
		(N, M) = map(int, input().split())
		NonSolid = [pow(L[m], N, P) for m in range(M + 1)]
		Solid = [0] * (M + 1)
		for m in range(M + 1):
			Solid[m] = NonSolid[m]
			for j in range(1, m):
				Solid[m] = (Solid[m] - Solid[j] * NonSolid[m - j]) % P
		print(Solid[M])
main()


ll = [0] * 1001
ll[0] = 1
ll[1] = 1
ll[2] = 2
ll[3] = 4
for g in range(4, 1001):
	ll[g] = (ll[g - 1] + ll[g - 2] + ll[g - 3] + ll[g - 4]) % 1000000007
a = int(input().strip())
l = []
for t in range(a):
	l.append(tuple(map(int, input().strip().split(' '))))
for i in l:
	S = []
	for tt in range(0, i[1] + 1):
		S.append(pow(ll[tt], i[0], 1000000007))
	U = [0, 0]
	for j in range(2, i[1] + 1):
		U.append(sum(((S[k] - U[k]) * S[j - k] for k in range(1, j))) % 1000000007)
	print((S[i[1]] - U[i[1]]) % 1000000007)


MOD = 1000000007
num_cases = int(input())
for i in range(num_cases):
	(N, M) = map(lambda s: int(s), input().split(' '))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	ntes = [0 for i in range(max(m + 1, 4))]
	(ntes[0], ntes[1], ntes[2], ntes[3]) = (1, 1, 2, 4)
	for i in range(4, m + 1):
		ntes[i] = (ntes[i - 1] + ntes[i - 2] + ntes[i - 3] + ntes[i - 4]) % 1000000007
	total = [pow(ntes[i], n, 1000000007) for i in range(m + 1)]
	validos = [0 for i in range(m + 1)]
	for i in range(1, m + 1):
		validos[i] = total[i]
		aux = 0
		for j in range(1, i):
			aux = (aux + validos[j] * total[i - j]) % 1000000007
		validos[i] = (validos[i] - aux) % 1000000007
	print(validos[m])


for _ in range(int(input())):
	modulo = 1000000007
	(n, m) = map(int, input().split())
	v = [1, 1, 2, 4]
	for w in range(4, m + 1):
		v.append(sum(v[-4:]) % modulo)
	row_combos = [pow(c, n, modulo) for c in v]
	non_solid = [0, 0]
	for i in range(2, m + 1):
		non_solid.append(sum(((row_combos[j] - non_solid[j]) * row_combos[i - j] for j in range(1, i))) % modulo)
	print((row_combos[m] - non_solid[m]) % modulo)


import sys
MOD = 1000000007
T = int(input())
for testcases in range(T):
	(N, M) = [int(z) for z in input().split()]
	rows = [1, 1, 2, 4]
	while len(rows) <= M:
		rows.append(sum(rows[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in rows]
	unstable = [0, 0, 1]
	for i in range(3, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


def get_walls(n, m):
	first = [1, 1, 2, 4]
	for i in range(4, m + 1):
		first.append(sum(first[-4:]) % 1000000007)
	table = [[1] * (m + 1)]
	for i in range(n):
		table.append([x * y % 1000000007 for (x, y) in zip(table[-1], first)])
	return table
walls = get_walls(1000, 1000)

def get_unbroken(n, m, walls=walls):
	unbroken = []
	wall = []
	for w in walls[n][1:m + 1]:
		total = sum((x * y for (x, y) in zip(unbroken, reversed(wall))))
		unbroken.append((w - total) % 1000000007)
		wall.append(w)
	return unbroken[-1]
t = int(input())
for test_case in range(t):
	(n, m) = input().strip().split()
	(n, m) = (int(n), int(m))
	print(get_unbroken(n, m))


T = int(input())
mu = 10 ** 9 + 7

def mod_pow(x, p):
	b = [int(d) for d in format(p, 'b')[::-1]]
	product = 1
	for i in range(0, len(b)):
		if not b[i]:
			continue
		factor = x % mu
		for j in range(i):
			factor = factor ** 2 % mu
		product = product * factor % mu
	return product
for t in range(T):
	(N, M) = [int(a) for a in input().split(' ')]
	row_ways = [0, 1]
	for m in range(2, M + 1):
		new = 1 if m <= 4 else 0
		row_ways.append((new + sum(row_ways[-4:])) % mu)
	all_walls = [mod_pow(x, N) for x in row_ways]
	solid = [None for __ in range(M + 1)]
	solid[1] = 1
	not_solid = [None for __ in range(M + 1)]
	not_solid[1] = 0
	for m in range(2, M + 1):
		accum = 0
		for m_prime in range(1, m):
			accum = (accum + solid[m_prime] * all_walls[m - m_prime] % mu) % mu
		not_solid[m] = accum
		solid[m] = (all_walls[m] - not_solid[m]) % mu
	print((all_walls[M] - not_solid[M]) % mu)


from array import array
mod = 1000000007
l = array('I', [1, 1, 2, 4] + [0] * 1500)
for i in range(4, 1500):
	for k in range(1, 5):
		l[i] += l[i - k]
	l[i] %= mod
T = int(input())
n = array('I', [1, 1] + [0] * 1500)
for a0 in range(T):
	(N, M) = input().split(' ')
	(N, M) = (int(N), int(M))
	p = array('I', [l[i] ** N % mod for i in range(len(l)) if i <= M])
	for i in range(2, M + 1):
		tmp = 0
		for k in range(1, i):
			tmp += n[i - k] * p[k]
		n[i] = (p[i] - tmp) % mod
	print(n[M] % mod)


P = 10 ** 9 + 7
MAX_M = 1000
nr_ways_ending = [0] * (MAX_M + 1)
nr_ways_ending[0] = 1
for i in range(MAX_M):
	for s in (1, 2, 3, 4):
		if i + s < MAX_M + 1:
			nr_ways_ending[i + s] += nr_ways_ending[i]

def solve(N, M):
	A = [0] * (M + 1)
	solution = [0] * (M + 1)
	solution[0] = 1
	for k in range(1, M + 1):
		A[k] = pow(nr_ways_ending[k], N, P)
		solution[k] = A[k]
		for j in range(1, k):
			solution[k] -= solution[j] * A[k - j]
		solution[k] %= P
	return solution[M] % P
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	print(solve(N, M))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


M = 10 ** 9 + 7
N = 1000
ways = [1] + [0] * N
for k in range(N):
	for b in (1, 2, 3, 4):
		if k + b <= N:
			ways[k + b] += ways[k]
	ways[k] %= M

def solve(height, width):
	combs = [pow(w, height, M) for w in ways]
	no_gaps = [0] * (width + 1)
	for w in range(1, width + 1):
		no_gaps[w] = combs[w] - sum((combs[w - i] * no_gaps[i] % M for i in range(1, w)))
		no_gaps[w] %= M
	return no_gaps[width]

def main():
	t = int(input())
	for _ in range(t):
		(height, width) = map(int, input().split())
		print(solve(height, width))
main()


def go(n, m):
	M = 1000000007
	f = [1, 1, 2, 4]
	for i in range(4, m + 1):
		f.append(sum(f[-4:]))
	F = [0, 1]
	for i in range(2, m + 1):
		v = f[i] = pow(f[i], n, M)
		for j in range(1, i):
			v -= F[j] * f[i - j]
		F.append(v % M)
	return F[-1]
for t in range(int(input())):
	print(go(*map(int, input().split())))


from functools import reduce
(M, r, A, B) = (10 ** 9 + 7, [1] * (1001 + 1), [1] * (1001 + 1), [0] * (1001 + 1))
(r[2], r[3]) = (2, 4)
for i in range(4, 1001):
	r[i] = reduce(lambda s, c: s + r[i - c], range(1, 5), 0)
powM = lambda b, e: b if e == 1 else (b if e & 1 else 1) * powM(b, e >> 1) ** 2 % M
for _ in range(int(input())):
	(n, m) = map(int, input().rstrip().split(' '))
	for i in range(2, m + 1):
		B[i] = reduce(lambda s, c: (s + A[c] * (A[i - c] + B[i - c])) % M, range(1, i), 0)
		A[i] = (powM(r[i], n) - B[i]) % M
	print((A[m] + M) % M)


MOD = 1000000007
A = [[0, 1, 2, 4, 8] + [0] * 996 for _ in range(1001)]
A[0] = [0] * 1001
for m in range(5, 1001):
	A[1][m] = (A[1][m - 1] + A[1][m - 2] + A[1][m - 3] + A[1][m - 4]) % MOD
for n in range(2, 1001):
	for m in range(1001):
		A[n][m] = A[n - 1][m] * A[1][m] % MOD

def solve(N, M):
	SN = [0] * 1001
	SN[1] = 1
	for m in range(2, M + 1):
		SN[m] = A[N][m]
		for i in range(1, m):
			SN[m] = (SN[m] - SN[i] * A[N][m - i]) % MOD
	return SN[M]

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = [int(i) for i in input().split()]
		print(solve(n, m))
main()


import os
import sys
MOD = 1000000007
A = int(sys.stdin.readline())
for _ in range(A):
	(X, Y) = list(map(int, sys.stdin.readline().split()))
	row = [1, 1, 2, 4]
	while len(row) <= Y:
		row.append(sum(row[-4:]) % MOD)
	total = [pow(c, X, MOD) for c in row]
	unstable = [0, 0]
	for i in range(2, Y + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[Y] - unstable[Y]) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


def go(n, m):
	M = 1000000007
	f = [1, 1, 2, 4]
	for i in range(4, m + 1):
		f.append(sum(f[-4:]))
	F = [0, 1]
	for i in range(2, m + 1):
		v = f[i] = pow(f[i], n, M)
		for j in range(1, i):
			v -= F[j] * f[i - j]
		F.append(v % M)
	return F[-1]
for t in range(int(input())):
	print(go(*map(int, input().split())))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	row_combinations = [1, 1, 2, 4]
	while len(row_combinations) <= M:
		row_combinations.append(sum(row_combinations[-4:]) % MOD)
	total = [pow(c, N, MOD) for c in row_combinations]
	unstable = [0, 0]
	for i in range(2, M + 1):
		unstable.append(sum(((total[j] - unstable[j]) * total[i - j] for j in range(1, i))) % MOD)
	print((total[M] - unstable[M]) % MOD)


import os
import sys
MOD = 1000000007
anywall_dp = [1]
for n in range(1, 1001):
	anywall_dp.append(sum((anywall_dp[m] for m in range(max(n - 4, 0), n))) % MOD)

def solidwall(h, w):
	anywall = [pow(anywall_dp[i], h, MOD) for i in range(w + 1)]
	dp = [0] * (w + 1)
	for wi in range(1, w + 1):
		dp[wi] = (anywall[wi] - sum((dp[w1] * anywall[wi - w1] for w1 in range(1, wi)))) % MOD
	return dp[-1]
t = int(input())
for t_itr in range(t):
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	print(solidwall(n, m))


def lego_blocks(N, M):
	S = [0 for _ in range(M)]
	P = [0 for _ in range(M)]
	Q = [0 for _ in range(M)]
	for i in range(M):
		Q[i] += pow(2, i) if i < 4 else Q[i - 1] + Q[i - 2] + Q[i - 3] + Q[i - 4]
		Q[i] %= 1000000007
	for i in range(M):
		P[i] = pow(Q[i], N, 1000000007)
	for i in range(M):
		S[i] = P[i]
		for j in range(1, i + 1):
			S[i] -= P[j - 1] * S[i - j]
			S[i] %= 1000000007
	return S[M - 1] % 1000000007

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = [int(i) for i in input().split()]
		print(lego_blocks(N, M))
main()


z = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	rc = [1, 1, 2, 4]
	while len(rc) <= m:
		rc.append(sum(rc[-4:]) % z)
	total = [pow(c, n, z) for c in rc]
	a = [0, 0]
	for i in range(2, m + 1):
		a.append(sum(((total[j] - a[j]) * total[i - j] for j in range(1, i))) % z)
	print((total[m] - a[m]) % z)


t = input()
mod = 1000000007

def fastPow(base, power, MOD):
	result = 1
	while power > 0:
		if power % 2 == 1:
			result = result * base % MOD
		power = power // 2
		base = base * base % MOD
	return result
for _ in range(int(t)):
	(n, m) = map(int, input().split())
	floorCombinations = [0] * 1001
	floorCombinations[0] = 0
	floorCombinations[1] = 1
	floorCombinations[2] = 2
	floorCombinations[3] = 4
	floorCombinations[4] = 8
	for i in range(5, 1001):
		floorCombinations[i] = (floorCombinations[i - 1] + floorCombinations[i - 2] + floorCombinations[i - 3] + floorCombinations[i - 4]) % mod
	dp = [0] * (m + 1)
	dp[0] = 0
	dp[1] = 1
	totalCases = [0] * (m + 1)
	for i in range(1, len(totalCases)):
		totalCases[i] = fastPow(floorCombinations[i], n, mod)
	for i in range(2, m + 1):
		dp[i] = totalCases[i]
		for ptr in range(1, i):
			dp[i] = (dp[i] - dp[ptr] * totalCases[i - ptr]) % mod
	print(dp[m] % mod)


__author__ = 'camilo ariza'
__email__ = 'camilo.ariza@protomail.com'
__created__ = 'Sat 04 Apr 2020 11:36:43 -0300'
__modified__ = 'Wed 08 Apr 2020 14:31:52 -0300'

def get_solid_walls(n, m, rows=[1, 1, 2, 4, 8]):
	mod = pow(10, 9) + 7
	(n, m) = (n % mod, m % mod)
	all_walls = [0] * (m + 1)
	solid_walls = [0] * (m + 1)
	len_rows = len(rows)
	rows += [0] * (m + 1 - len_rows)
	for i in range(1, m + 1):
		if i >= len_rows:
			rows[i] = (rows[i - 1] + rows[i - 2] + rows[i - 3] + rows[i - 4]) % mod
		solid_walls[i] = all_walls[i] = pow(rows[i], n) % mod
		for j in range(1, i):
			solid_walls[i] = (solid_walls[i] - solid_walls[j] * all_walls[i - j]) % mod
	return solid_walls[m]
t = int(input())
for _ in range(t):
	print(get_solid_walls(*map(int, input().split())))