Stephanie just learned about a game called Nim in which there are two players and $n$ piles of stones. During each turn, a player must choose any non-empty pile and take as many stones as they want. The first player who cannot complete their turn (i.e., because all piles are empty) loses.  

Stephanie knows that, for each start position in this game, it's possible to know which player will win (i.e., the first or second player) if both players play optimally. Now she wants to know the number of different games that exist that satisfy all of the following conditions:

The game starts with $n$ non-empty piles and each pile contains less than $2^{m}$ stones.
All the piles contain pairwise different numbers of stones.
The first player wins if that player moves optimally.

Help Stephanie by finding and printing the number of such games satisfying all the above criteria, modulo $10^9+7$.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ and $m$.

Constraints

$1\leq n,m\leq10^7$  

Output Format

Print the number of such games, modulo $10^9+7$.

Sample Input 0
2 2

Sample Output 0
6

Explanation 0

We want to know the number of games with $n=2$ piles where each pile contains $<2^m=2^2=4$ stones. There are six such possible games with the following distributions of stones: $(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)$. Thus, we print the result of $6\ \text{mod}\ (10^9+7)=6$ as our answer.

Source: hackerrank | Difficulty: HARD
Tags: Game theory


Solutions:
_ = input().split()
mod = 10 ** 9 + 7
n = int(_[0])
m = int(_[1])
M = pow(2, m, mod) - 1
comb_n_1 = M % mod * ((M - 1) % mod)
nim_n_2 = 0
nim_n_1 = 0
nim_n = 0
if n == 1:
	print(M % mod)
elif n == 2:
	print(M % mod * ((M - 1) % mod) % mod)
else:
	for i in range(3, n + 1):
		nim_n = (comb_n_1 - nim_n_1 - nim_n_2 * (M - i + 2) * (i - 1)) % mod
		comb_n_1 = comb_n_1 * (M - i + 1) % mod
		nim_n_2 = nim_n_1
		nim_n_1 = nim_n
	print((comb_n_1 - nim_n) % mod)


_ = input().split()
mod = 10 ** 9 + 7
n = int(_[0])
m = int(_[1])
M = pow(2, m, mod) - 1
comb_n_1 = M % mod * ((M - 1) % mod)
nim_n_2 = 0
nim_n_1 = 0
nim_n = 0
if n == 1:
	print(M % mod)
elif n == 2:
	print(M % mod * ((M - 1) % mod) % mod)
else:
	for i in range(3, n + 1):
		nim_n = (comb_n_1 - nim_n_1 - nim_n_2 * (M - i + 2) * (i - 1)) % mod
		comb_n_1 = comb_n_1 * (M - i + 1) % mod
		nim_n_2 = nim_n_1
		nim_n_1 = nim_n
	print((comb_n_1 - nim_n) % mod)


_ = input().split()
mod = 10 ** 9 + 7
n = int(_[0])
m = int(_[1])
M = pow(2, m, mod) - 1
comb_n_1 = M % mod * ((M - 1) % mod)
nim_n_2 = 0
nim_n_1 = 0
nim_n = 0
if n == 1:
	print(M % mod)
elif n == 2:
	print(M % mod * ((M - 1) % mod) % mod)
else:
	for i in range(3, n + 1):
		nim_n = (comb_n_1 - nim_n_1 - nim_n_2 * (M - i + 2) * (i - 1)) % mod
		comb_n_1 = comb_n_1 * (M - i + 1) % mod
		nim_n_2 = nim_n_1
		nim_n_1 = nim_n
	print((comb_n_1 - nim_n) % mod)


import sys
(n, m) = map(int, sys.stdin.readline().split())
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = map(int, sys.stdin.readline().split())
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import os
import sys
i = input().split()
mod = 10 ** 9 + 7
a = int(i[0])
m = int(i[1])
M = pow(2, m, mod) - 1
comb_n_1 = M % mod * ((M - 1) % mod)
nim_n_2 = 0
nim_n_1 = 0
nim_n = 0
if a == 1:
	print(M % mod)
elif a == 2:
	print(M % mod * ((M - 1) % mod) % mod)
else:
	for i in range(3, a + 1):
		nim_n = (comb_n_1 - nim_n_1 - nim_n_2 * (M - i + 2) * (i - 1)) % mod
		comb_n_1 = comb_n_1 * (M - i + 1) % mod
		nim_n_2 = nim_n_1
		nim_n_1 = nim_n
	print((comb_n_1 - nim_n) % mod)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pm(x, y, z):
	num = 1
	while y:
		if y & 1:
			num = num * x % z
		y >>= 1
		x = x * x % z
	return num
S = pm(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
w = S
z1 = pm(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - w) * x % p
	S = S * x % p
	w = S - A1
	A1 = w - A3
print(w % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pm(x, y, z):
	num = 1
	while y:
		if y & 1:
			num = num * x % z
		y >>= 1
		x = x * x % z
	return num
S = pm(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
w = S
z1 = pm(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - w) * x % p
	S = S * x % p
	w = S - A1
	A1 = w - A3
print(w % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
s = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = s
W = s
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (s - W) * x % p
	s = s * x % p
	W = s - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(A, B) = list(map(int, sys.stdin.readline().split()))
C = 1000000007

def power(P, Q, R):
	NUM = 1
	while Q:
		if Q & 1:
			NUM = NUM * P % R
		Q >>= 1
		P = P * P % R
	return NUM
S = power(2, B, C) - 1 % C
L1 = 0
L2 = 0
L3 = S
O = S
U1 = power(2, B, C)
P = U1 - 1
for i in range(2, A + 1):
	P -= 1
	L3 = i * (S - O) * P % C
	S = S * P % C
	O = S - L1
	L1 = O - L3
print(O % C)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(p, q, r):
	number = 1
	while q:
		if q & 1:
			number = number * p % r
		q >>= 1
		p = p * p % r
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pM(x, y, z):
	q = 1
	while y:
		if y & 1:
			q = q * x % z
		y >>= 1
		x = x * x % z
	return q
S = pM(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
w = pM(2, m, p)
x = w - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, b) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, b, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, b, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)


import sys
(n, m) = list(map(int, sys.stdin.readline().split()))
p = 1000000007

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
S = pow_mod(2, m, p) - 1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2, m, p)
x = z1 - 1
for i in range(2, n + 1):
	x -= 1
	A3 = i * (S - W) * x % p
	S = S * x % p
	W = S - A1
	A1 = W - A3
print(W % p)