import sys
readline = sys.stdin.readline
MOD = 10**9+7
H, W = map(int, readline().split())
K = 3
def zti(z):
res = 0
for zi in z:
res *= K
res += zi
return res
def itz(i):
res = []
for _ in range(H):
res.append(i%K)
i //= K
return res[::-1]
def check(z):
for zi, zj in zip(z, z[1:]):
if zi and zj and zi != zj:
return False
if zi >= 2 and z.count(zi) == 1:
return False
return True
Di = dict()
cnt = 0
D = []
for i in range(K**H):
s = itz(i)
if 1 in s and check(s):
Di[i] = cnt
cnt += 1
D.append(i)
class UF():
def __init__(self, col):
self.par = [-1]*len(col)
self.col = col
for i in range(len(col)):
for j in range(i):
if col[i] and col[i] == col[j]:
self.union(i, j)
def find(self, x):
if self.par[x] < 0:
return x
else:
stack = []
while self.par[x] >= 0:
stack.append(x)
x = self.par[x]
for xi in stack:
self.par[xi] = x
return x
def union(self, x, y):
rx = self.find(x)
ry = self.find(y)
if rx != ry:
if self.par[rx] > self.par[ry]:
rx, ry = ry, rx
self.par[rx] += self.par[ry]
self.par[ry] = rx
if not self.col[rx]:
res = self.col[ry]
elif self.col[ry]:
res = min(self.col[rx], self.col[ry])
else:
res = self.col[rx]
self.col[rx] = res
return rx
def compress(L):
L2 = list(set(L))
L2.sort()
C = {v : k for k, v in enumerate(L2)}
return L2, C
Edge = [[0]*cnt for _ in range(cnt)]
for idx in range(cnt):
i = D[idx]
for S in range(1<<H):
T = UF(itz(i))
for j in range(H-1):
if (1<<j)&S and (1<<j+1)&S:
T.union(j, j+1)
res = [None]*H
cc = 10
for j in range(H):
if not (1<<j)&S:
res[j] = 0
else:
c = T.col[T.find(j)]
if c:
res[j] = c
else:
res[j] = cc
T.col[T.find(j)] = cc
cc += 1
#print(1, itz(D[idx]), format(S, 'b').zfill(H)[::-1], res)
if 1 not in res:
continue
for k in range(H):
r = res[k]
if r >= 2 and res.count(r) == 1:
res[k] = 0
_, Cd = compress(res + [0])
res = [Cd[r] for r in res]
ri = zti(res)
if ri not in Di:
continue
Edge[Di[ri]][idx] += 1
def mat_dot(A, B):
assert len(A[0]) == len(B), 'invalid_size'
L = len(A)
M = len(A[0])
N = len(B[0])
res = [[0]*N for _ in range(L)]
for i in range(L):
for j in range(N):
a = 0
for k in range(M):
a = (a+A[i][k]*B[k][j]) % MOD
res[i][j] = a
return res
def mat_pow(A, x):
N = len(A)
res = [[0]*N for _ in range(N)]
for i in range(N):
res[i][i] = 1
for i in range(x.bit_length()):
if 2**i & x:
res = mat_dot(res, A)
A = mat_dot(A, A)
return res
dp = [0]*cnt
dp[Di[zti(tuple([1] + [0]*(H-1)))]] = 1
dp = mat_dot(mat_pow(Edge, W), [[d] for d in dp])
ans = 0
for idx in range(cnt):
if itz(D[idx])[-1] == 1:
ans = (ans + dp[idx][0])%MOD
print(ans)