A few days ago Chef decided to cook a new dish – chocolate.  This must be something amazing. The idea is that chocolate bar will be divided into cells. It must be long, but narrow. To interest customers every bar must be unique. Bar will consist of cells of black or white chocolate. In addition every bar must be good looking. It means that the bar must not contain any totally white or totally black rectangle, whose width and length are more than 1 (Note that a bar is good if (width > 1 and length = 1) or (length > 1 and width = 1)). Now, Chef wants to know how many bars can he cook? He’s not good in computer programming, so this task is for you.
 By the way, it's not permitted to rorate bars. It means that WBB and BBW are different bars.

Input

Input contains two integers: width a (1 ≤ a ≤ 6) and length b (1 ≤ b < 2^63).

Output

Print in output a single integer which is the answer. Answer can be a very big number, so print it modulo 10^9+7 (1000000007).

Example

Input:
2 2

Output:
14

Input:
3 3

Output:
322

Explanation

In the first sample, there are 2^(2*2) = 16 ways coloring the chocolate in total, and the only following 2 chocolates are not good


WW
WW
The bar contains a totally white rectangle of length = 2 and width = 2.

BB
BB
The bar contains a totally black rectangle of length = 2 and width = 2.
#!/usr/bin/python
mod = 1000000007
#import psyco
#psyco.full()
def matrix_mult(A, B):
  C = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
  for i in range(3):
	  for j in range(3):
		  for k in range(3):
			  C[i][k] = (C[i][k] + A[i][j] * B[j][k])
	  	          if(C[i][k] > 1000000007):
				C[i][k] = C[i][k] % 1000000007
  return C

def matrix_mult_1(A, B):
  C = [[0, 0],[0,0]]
  for i in range(2):
	  for j in range(2):
		  for k in range(2):
			  C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % 1000000007
  return C

def matrix_mult_4(A, B):
  C = [[0, 0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
  for i in range(5):
	  for j in range(5):
		  for k in range(5):
			  C[i][k] = (C[i][k] + A[i][j] * B[j][k])
		          if(C[i][k] > 1000000007):
				C[i][k] = C[i][k] % 1000000007
  return C

def matrix_mult_5(A,B):
  C=[]
  for i in range(9):
	  C.append([0,0,0,0,0,0,0,0,0])
  for i in range(9):
	  for j in range(9):
		  for k in range(9):
			  C[i][k] = (C[i][k] + A[i][j] * B[j][k])
		          if(C[i][k] > 1000000007):
				C[i][k] = C[i][k] % 1000000007
  return C

def matrix_mult_6(A,B):
  C=[]
  for i in range(18):
	  C.append([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])
  for i in range(18):
	  for j in range(18):
		  for k in range(18):
			  #if( A[i][j] > mod):
		#		  A[i][j] = A[i][j] % mod
		#	  elif (B[j][k] > mod):
		#		  B[j][k] = B[j][k] % mod
			  C[i][k] = (C[i][k] + A[i][j] * B[j][k])
	       #           if(C[i][k] > mod):
			  C[i][k] = C[i][k] % mod
  return C

def fast_exp(A, n, flag):
  if n == 1:
	return A
  else:
    if n & 1 == 0:
      A1 = fast_exp(A, n/2,flag)
      if(flag == 2):
	      return matrix_mult_1(A1, A1)
      elif (flag == 3):
	      return matrix_mult(A1,A1)
      elif (flag == 4):
	      return matrix_mult_4(A1,A1)
      elif( flag == 5):
	      return matrix_mult_5(A1,A1)
      elif (flag == 6):
	      return matrix_mult_6(A1,A1)
    else:
      A1 = fast_exp(A,n-1,flag)
      if(flag == 2):
	      return matrix_mult_1(A,A1)
      elif(flag == 3):
	      return matrix_mult(A,A1)
      elif(flag == 4):
	      return matrix_mult_4(A,A1)
      elif(flag == 5):
	      return matrix_mult_5(A,A1)
      elif(flag == 6):
	      return matrix_mult_6(A,A1)

def fast_pow(n):
  if n == 1:
	return 2
  if n == 0:
        return 1
  else:
    if n % 2 == 0:
		        ans = fast_pow(n/2)
      		   	ans = ans % mod
     			return (ans*ans) % mod
    else:
			ans = fast_pow(n-1)
		        ans = ans % mod
		        return ans*2

def solve_1(n):
    A = [[0,1,0],[0,0,1],[1,1,1]]
    A_n = fast_exp(A,n-3)
    return A_n[2][0] + A_n[2][1] + A_n[2][2]*2

def solve_2(n):
    if(n == 1):
	    return 2
    elif(n == 2):
	    return 7
    A = [[0,1],[2,3]]
    A_n = fast_exp(A,n-2,2)
    return A_n[1][0]*2 + A_n[1][1]*7

def solve_3(n):
    A = [[0,1,0],[0,0,1],[-2,3,6]]
    if(n == 1):
	    return 4
    elif(n == 2):
	    return 25
    elif(n == 3):
    	    return 161
    A_n = fast_exp(A,n-3,3)
    return A_n[2][0]*4 + A_n[2][1]*25 + A_n[2][2]*161

def solve_4(n):
    ans= [8,89,1033,11929,137845]
    if(n <= 5):
	    return ans[n-1]
    A = [[0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1],[8,-30,-21,20,10]]
    A_n = fast_exp(A,n-5,4)
    return A_n[4][0]*8 + A_n[4][1]*89 + A_n[4][2]*1033 + A_n[4][3]*11929 + A_n[4][4]* 137845

def solve_5(n):
    ans = [16,317,6631,137845,2867739,59655167,1240971177,25815151595,537016650729]
    if(n <= 9):
	    return ans[n-1]
    A = [[0,1,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0],[0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,0,0,0],[0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,1],[-10,69,29,-662,790,73,-278,9,21]]
    Ab = fast_exp(A,n-9,5)
    return Ab[8][0]*16 + Ab[8][1]*317+ Ab[8][2]*6631+ Ab[8][3]*137845+Ab[8][4]*2867739+Ab[8][5]*59655167 + Ab[8][6]*1240971177 + Ab[8][7]* 25815151595 + Ab[8][8]*537016650729 

def solve_6(n):
	ans =[32,1129,42563,1592731,59655167,2234126207,83670667271,3133560234217,117355367786585,4395090865370635,164601109918978615,6164497208894901477,230867373009598884627,8646243499452479433569,323811570588787197424201,12127108524504811121752257,454173891617617632766031151,17009324474195992258878836533]
	if(n <= 18):
		return ans[n-1]
	for i in range(18):
		ans[i] = ans[i] % mod
	A=[[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]]
	A.append([28,-622,3386,6203,-70276,38077,355981,-410368,-499260,751787,154999,-396016,27152,50702,-3905,-2391,120,36])
        Ab = fast_exp(A,n-18,6)
	#print len(ans)
	finalans = 0
	for i in range(18):
		finalans = finalans + ((Ab[17][i] % mod)*ans[i]) % mod
		if(finalans > mod):
			finalans % mod
	return finalans
inp = raw_input()
inp = inp.split()
#print inp[0],inp[1]
inp[0] = int(inp[0]); inp[1] = int(inp[1]);
if(inp[0] == 1):
	if(inp[1] == 1):
		print 2
	else:
		print fast_pow(inp[1])%mod
elif(inp[0] == 2):
	print (solve_2(inp[1])*2)%mod
elif(inp[0] == 3):
	print (solve_3(inp[1])*2)%mod
elif(inp[0] == 4):
	print (solve_4(inp[1])*2)%mod
elif(inp[0] == 5):
	print (solve_5(inp[1])*2)%mod
elif(inp[0] == 6):
	print (solve_6(inp[1])*2)%mod