MOD = 1_000_000_007 def to(H, A): """ empty col """ if A == 'begin': yield 'begin' elif A == 'end': yield 'end' elif len(set(x for x in A if x >= 0)) == 1: yield 'end' if A == 'end': return _A = A for s in range(1, 1 << H): if _A == 'begin' or _A == 'end': A = [-1] * H else: A = list(_A) for i in range(H): if A[i] >= 0: A[i] += H for i in range(H): if s & 1 << i: A.append(i) else: A.append(-1) """ 横にマージ """ for i in range(H): j = i + H if A[i] >= 0 and A[j] >= 0 and A[i] != A[j]: before = max(A[i], A[j]) after = min(A[i], A[j]) for k in range(H + H): if A[k] == before: A[k] = after """ 縦にマージ """ for i in range(H, H + H - 1): j = i + 1 if A[i] >= 0 and A[j] >= 0 and A[i] != A[j]: before = max(A[i], A[j]) after = min(A[i], A[j]) for k in range(H + H): if A[k] == before: A[k] = after if any(x >= H for x in A[:H]): # 孤立した連結成分が残ってしまった場合 continue yield tuple(A[H:]) def flip(A): H = len(A) A = list(A[::-1]) for i in range(H): if A[i] != -1: A[i] = H - 1 - A[i] for i in range(H): if A[i] > i: before = A[i] after = i for j in range(H): if A[j] == before: A[j] = after return tuple(A) def generate_graph(H): """ mirror reflection を同一視して、状態を圧縮する """ V = ['begin', 'end'] ID = {'begin': 0, 'end': 1} G = [] for i, v in enumerate(V): for w in to(H, v): if w not in ID: ID[w] = len(V) V.append(w) j = ID[w] G.append((i, j)) return len(V), G def conv(A, B): C = [0] * (len(A) + len(B) - 1) for i in range(len(A)): for j in range(len(B)): C[i + j] += A[i] * B[j] C[i + j] %= MOD return C def coef_of_generating_function(P, Q, N): assert Q[0] == 1 and len(Q) == len(P) + 1 while N: Q1 = Q.copy() for i in range(len(Q)): if i & 1: Q1[i] = -Q1[i] P = conv(P, Q1)[N & 1::2] Q = conv(Q, Q1)[::2] N >>= 1 return P[0] def find_generating_function(A): N = len(A) B = [1] C = [1] l, m, p = 0, 1, 1 for i in range(N): d = A[i] for j in range(1, l + 1): d += C[j] * A[i - j] d %= MOD if d == 0: m += 1 continue T = C.copy() q = pow(p, MOD - 2, MOD) * d % MOD if len(C) < len(B) + m: C += [0] * (len(B) + m - len(C)) for j in range(len(B)): C[j + m] -= q * B[j] C[j + m] %= MOD if l + l <= i: B = T l, m, p = i + 1 - l, 1, d else: m += 1 Q = C P = conv(A, Q)[:len(Q) - 1] return P, Q def solve_small(H): N, G = generate_graph(H) FRM, TO = map(list, zip(*G)) MAX = N + N + 10 ans = [0] * MAX dp = [0] * N dp[0] = 1 for i in range(MAX): newdp = [0] * N for a, b in G: newdp[b] += dp[a] dp = [x % MOD for x in newdp] ans[i] = dp[1] return ans H, W = map(int, input().split()) A = solve_small(H) P, Q = find_generating_function(A) print(coef_of_generating_function(P, Q, W))