A sequence of non-negative integers a_1, a_2, ..., a_{n} of length n is called a wool sequence if and only if there exists two integers l and r (1 ≤ l ≤ r ≤ n) such that $a_{l} \oplus a_{l + 1} \oplus \cdots \oplus a_{r} = 0$. In other words each wool sequence contains a subsequence of consecutive elements with xor equal to 0.

The expression $x \oplus y$ means applying the operation of a bitwise xor to numbers x and y. The given operation exists in all modern programming languages, for example, in languages C++ and Java it is marked as "^", in Pascal — as "xor".

In this problem you are asked to compute the number of sequences made of n integers from 0 to 2^{m} - 1 that are not a wool sequence. You should print this number modulo 1000000009 (10^9 + 9).


-----Input-----

The only line of input contains two space-separated integers n and m (1 ≤ n, m ≤ 10^5).


-----Output-----

Print the required number of sequences modulo 1000000009 (10^9 + 9) on the only line of output.


-----Examples-----
Input
3 2

Output
6



-----Note-----

Sequences of length 3 made of integers 0, 1, 2 and 3 that are not a wool sequence are (1, 3, 1), (1, 2, 1), (2, 1, 2), (2, 3, 2), (3, 1, 3) and (3, 2, 3).

Difficulty: EASY
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
(n, m) = map(int, input().split())
k = pow(2, m, 1000000009) - 1
ans = 1
for i in range(n):
	ans = ans * (k - i) % 1000000009
print(ans)


(n, m) = map(int, input().split())
mod = 10 ** 9 + 9
(s, ans) = (pow(2, m, mod) - 1, 1)
for i in range(n):
	ans = ans * (s - i) % mod
print(ans)


(a, b) = map(int, input().split())
ans = 1
mod = 1000000009
gh = pow(2, b, mod)
for i in range(1, 1 + a):
	ans = pow(ans * (gh - i), 1, mod)
print(ans)


MOD = 10 ** 9 + 9
(n, m) = map(int, input().split())
p = pow(2, m, MOD)
ans = 1
for i in range(1, n + 1):
	ans = ans * (p - i) % MOD
print(ans)


(n, m) = list(map(int, input().split()))
MOD = 10 ** 9 + 9
out = 1
curr = pow(2, m, MOD) - 1
for i in range(n):
	out *= curr
	curr -= 1
	out %= MOD
print(out)


MOD = int(1000000000.0 + 9)

def fast_power(b, e):
	res = 1
	while e:
		if e % 2 == 1:
			res = res * b % MOD
		b = b * b % MOD
		e >>= 1
	return res
(n, m) = map(int, input().split())
a = fast_power(2, m) - 1
a = (a + MOD) % MOD
b = a - 1
b = (b + MOD) % MOD
for i in range(1, n):
	a = a * b % MOD
	b = (b - 1 + MOD) % MOD
print(a)


(n, m) = map(int, input().split())
MOD = 1000000009
o = 1
m = pow(2, m, MOD) - 1
for i in range(n):
	o = o * (m - i) % MOD
print(o)


(n, m) = map(int, input().split())
mod = 1000000009
upper = pow(2, m, mod)
s = 1
for i in range(0, n):
	s = s * (upper - i - 1) % mod
print(s)


(n, m) = map(int, input().split())
MOD = 10 ** 9 + 9
ans = pow(2, m, MOD) - 1
step = pow(2, m, MOD) - 2
for i in range(n - 1):
	ans = ans * step % MOD
	step -= 1
while ans < 0:
	ans += MOD
while ans >= MOD:
	ans -= MOD
print(ans)


e = 10 ** 9 + 9
(n, m) = map(int, input().split())
t = pow(2, m, e)
r = 1
for i in range(n):
	r = r * (t - i - 1) % e
print(r)


(n, m) = list(map(int, input().split()))
ans = pow(2, m, 10 ** 9 + 9)
ans -= 1
ans %= 10 ** 9 + 9
x = ans - 1
x %= 10 ** 9 + 9
for i in range(1, n):
	ans *= x
	ans %= 10 ** 9 + 9
	x -= 1
	x %= 10 ** 9 + 9
print(ans)


def fastExpMod(b, e, m):
	result = 1
	while e != 0:
		if e & 1 == 1:
			result = result * b % m
		e >>= 1
		b = b * b % m
	return result

def main():
	(n, m) = map(int, input().strip().split())
	mod = int(1000000000.0 + 9)
	ans = (fastExpMod(2, m, mod) - 1) % mod
	temp = (ans - 1 + mod) % mod
	for i in range(2, n + 1):
		ans = (ans * temp % mod + mod) % mod
		temp = temp - 1
		temp = (temp + mod) % mod
	ans = int(ans % mod)
	print(ans)
main()


(n, m) = map(int, input().split())
(s, d) = (1, 1000000009)
k = pow(2, m, d) - 1
for i in range(n):
	(s, k) = (s * k % d, k - 1)
print(s)