Madoka decided to entrust the organization of a major computer game tournament "OSU"!

In this tournament, matches are held according to the "Olympic system". In other words, there are $2^n$ participants in the tournament, numbered with integers from $1$ to $2^n$. There are $n$ rounds in total in the tournament. In the $i$-th round there are $2^{n - i}$ matches between two players (one of whom is right, the other is left), after which the winners go further along the tournament grid, and the losing participants are eliminated from the tournament. Herewith, the relative order in the next round does not change. And the winner of the tournament — is the last remaining participant.

But the smaller the participant's number, the more he will pay Madoka if he wins, so Madoka wants the participant with the lowest number to win. To do this, she can arrange the participants in the first round as she likes, and also determine for each match who will win — the participant on the left or right.

But Madoka knows that tournament sponsors can change the winner in matches no more than $k$ times. (That is, if the participant on the left won before the change, then the participant on the right will win after the change, and if the participant on the right won, then the participant on the left will win after the change).

So, the first image shows the tournament grid that Madoka made, where the red lines denote who should win the match. And the second one shows the tournament grid, after one change in the outcome of the match by sponsors (a match between $1$ and $3$ players).

Print the minimum possible number of the winner in the tournament, which Madoka can get regardless of changes in sponsors. But since the answer can be very large, output it modulo $10^9 + 7$. Note that we need to minimize the answer, and only then take it modulo.


-----Input-----

The first and the only line contains two integers $n$ and $k$ ($1 \le n \le 10^5, 1 \le k \le \min(2^n - 1, 10^9)$) — the number of rounds in the tournament and the number of outcomes that sponsors can change.


-----Output-----

Print exactly one integer — the minimum number of the winner modulo $10^9 + 7$


-----Examples-----

Input
1 1
Output
2
Input
2 1
Output
3
Input
3 2
Output
7


-----Note-----

In the first example, there is only one match between players $1$ and $2$, so the sponsors can always make player $2$ wins.

The tournament grid from the second example is shown in the picture in the statement.

Difficulty: HARD
Tags: Constructive algorithms

Combinatorics

Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
def corruption(n, k):
	MOD = 10 ** 9 + 7
	if k >= n:
		return 2 ** n % MOD
	res = 1
	choose = 1
	for i in range(1, k + 1):
		choose = choose * (n - i + 1) * pow(i, -1, MOD) % MOD
		res = (res + choose) % MOD
	return res
(n, k) = tuple(map(int, input().split()))
print(corruption(n, k))


def solve():
	mod = 1000000007
	(n, k) = map(int, input().strip().split())
	res = pow(2, n, mod)
	if k >= n:
		print(res)
	elif k + 1 == n:
		print(res - 1)
	else:
		f = [1 for i in range(n + 1)]
		fi = [1 for i in range(n + 1)]
		for i in range(1, n + 1):
			f[i] = f[i - 1] * i % mod
		fi[n] = pow(f[n], mod - 2, mod)
		for i in range(n - 1, 0, -1):
			fi[i] = fi[i + 1] * (i + 1) % mod
		ans = 0
		for i in range(0, k + 1):
			ans += f[n] * fi[n - i] * fi[i] % mod
			ans %= mod
		print(ans)
solve()


(n, k) = map(int, input().split())
ans = 1
s = 1
y = k - (k - n // 2)
h = min(n // 2 + (n % 2 == 1) + 1, k + 1)
if k < n:
	if k + 1 == h:
		for i in range(1, h):
			s = s * (n - i + 1) * pow(i, -1, 10 ** 9 + 7) % (10 ** 9 + 7)
			ans += s
			if y > 0 and i > y and (h - 1 != i):
				ans += s
		print(ans % (10 ** 9 + 7))
	else:
		for i in range(1, n - k):
			s = s * (n - i + 1) * pow(i, -1, 10 ** 9 + 7) % (10 ** 9 + 7)
			ans += s
			if y > 0 and i > y and (h - 1 != i):
				ans += s
		print((pow(2, n) - ans) % (10 ** 9 + 7))
else:
	print(pow(2, n, 10 ** 9 + 7))


import sys

def solve():
	inp = sys.stdin.readline
	(n, k) = map(int, inp().split())
	MOD = int(1000000000.0 + 7)
	if k >= n:
		print(pow(2, n, MOD))
		return
	F = [None] * (n + 1)
	F[0] = 1
	for i in range(1, n + 1):
		F[i] = F[i - 1] * i % MOD
	FI = [None] * (n + 1)
	FI[n] = pow(F[n], MOD - 2, MOD)
	FI[0] = 1
	for i in range(n - 1, 0, -1):
		FI[i] = FI[i + 1] * (i + 1) % MOD
	r = 0
	for i in range(0, k + 1):
		r = (r + F[n] * FI[n - i] * FI[i]) % MOD
	print(r)

def main():
	solve()
main()


(n, k) = [int(e) for e in input().split()]
k = min(k, n)
result = 1
c = 1
modulo = 10 ** 9 + 7
inv = [0 for i in range(k + 1)]
inv[0] = 1
if k + 1 >= 2:
	inv[1] = 1
for i in range(2, k + 1):
	inv[i] = modulo - modulo // i * inv[modulo % i] % modulo
for m in range(1, k + 1):
	c = c * (n - m + 1) * inv[m]
	c %= modulo
	result = (result + c) % modulo
print(result)


MOD = 10 ** 9 + 7
MAX_F = 10 ** 5 + 5
fact = [1 for i in range(MAX_F)]
ifact = [1 for i in range(MAX_F)]

def mult(a, b):
	return a * b % MOD

def power(a, n):
	if n == 0:
		return 1
	tmp = power(a, n // 2)
	if n % 2 == 0:
		return mult(tmp, tmp) % MOD
	return mult(a, mult(tmp, tmp)) % MOD

def C(n, k):
	if k < 0 or k > n:
		return 0
	return mult(fact[n], mult(ifact[n - k], ifact[k]))

def init():
	n = MAX_F - 1
	for i in range(1, n + 1):
		fact[i] = mult(fact[i - 1], i)
	ifact[n] = power(fact[n], MOD - 2)
	for i in range(n - 1, 0, -1):
		ifact[i] = mult(ifact[i + 1], i + 1)
init()
(n, k) = map(int, input().split())
res = 0
for m in range(min(n, k) + 1):
	res += C(n, m)
	res = res % MOD
print(res)


import sys
input = sys.stdin.readline

def int_num():
	return int(input())

def int_list():
	return list(map(int, input().split()))

def str_list():
	s = input()
	return list(s[:len(s) - 1])

def instr():
	return input().strip()

def invr():
	return map(int, input().split())

def cal_c1(n, k):
	MOD = 10 ** 9 + 7
	k = min(n, k)
	ans = 1
	da = 1
	for i in range(1, k + 1):
		da *= n + 1 - i
		da %= MOD
		t = pow(i, -1, MOD)
		da *= t
		da %= MOD
		ans += da
		ans %= MOD
	return ans

def solve():
	(n, k) = int_list()
	ans = cal_c1(n, k)
	print(ans)

def main():
	solve()
main()


(n, k) = map(int, input().split())
x = 0
y = 1
mod = 10 ** 9 + 7
for i in range(min(n, k) + 1):
	x = (x + y) % mod
	y = y * (n - i) * pow(i + 1, -1, mod) % mod
print(x)


(n, k) = map(int, input().split())
binom = 1
curNum = n
curDeNum = 1
rem = 0
c = 0
while k >= 0 and c <= n:
	c += 1
	k -= 1
	rem = (rem + binom) % 1000000007
	binom = binom * curNum * pow(curDeNum, -1, 1000000007) % 1000000007
	curNum -= 1
	curDeNum += 1
print(rem)


(n, k) = map(int, input().split())
ans = 0
cur = 0
for i in range(0, min(n, k) + 1):
	if i == 0:
		ans += 1
		cur = 1
	else:
		cur *= n - (i - 1)
		cur *= pow(i, -1, 1000000007)
		cur = cur % 1000000007
		ans += cur
		ans = ans % 1000000007
print(ans)


(welln, kwell) = map(int, input().split())
kwell = min(kwell, welln)
wellMODwell = 10 ** 9 + 7
counwellt = 0
wellc = 1
for i in range(kwell + 1):
	counwellt = (counwellt + wellc) % wellMODwell
	wellc = wellc * (welln - i) * pow(i + 1, wellMODwell - 2, wellMODwell) % wellMODwell
print(counwellt)


(n, k) = map(int, input().split())
k = min(k, n)
MOD = 10 ** 9 + 7
count = 0
c = 1
for i in range(k + 1):
	count = (count + c) % MOD
	c = c * (n - i) * pow(i + 1, MOD - 2, MOD) % MOD
print(count)


def solve():
	mod = 1000000007
	(n, k) = map(int, input().strip().split())
	res = pow(2, n, mod)
	if k >= n:
		print(res)
	elif k + 1 == n:
		print(res - 1)
	else:
		ans = 1
		temp1 = 1
		temp2 = 1
		for i in range(1, n - k):
			temp1 *= n - i + 1
			temp1 %= mod
			temp2 *= i
			temp2 %= mod
			ans += temp1 * pow(temp2, mod - 2, mod) % mod
		print((res - ans + mod) % mod)
solve()