Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef is an intern at Zoozle. He has a co-intern named Ajar who's good at maths. Chef wants to impress Ajar with his zoozliness, so he decided to play the following game with A
Consider $n$ force vectors in a 2D plane.
First, Ajar uniformly randomly chooses a non-negative real *magnitude* for each vector such that the sum of all magnitudes is equal to $k$. (More formally, each valid $n$-tuple of magnitudes can be chosen with the same probability.)
Then, Chef must choose a *direction* for each force vector in such a way that the net force (vector sum of all forces) is equal to zero. Chef wins the game if he is able to do that; otherwise, Ajar wins the game.

Since Chef knows that it may not always be possible to choose the directions such that he wins the game, he would like to know the probability that he'll be able to win if he plays optimally. Can you help him?

It can be proven that this probability can be written as a fraction $P/Q$, where $P ≥ 0$ and $Q > 0$ are coprime integers. Since we are in the 21st century, nobody is interested in fractions. Therefore, you should compute $P\cdot Q^{-1}$ modulo $10^{9}+7$, where $Q^{-1}$ denotes the modular inverse of $Q$ modulo $10^{9}+7$. (It is guaranteed that this inverse exists and is unique.)

------  Input ------
The first line of the input contains a single integer $n$ denoting the number of force vectors.
The second line contains a single integer $k$ denoting the sum of magnitudes of all force vectors.

------  Output ------
Print a single line containing one integer — the value of $P\cdot Q^{-1}$ modulo $10^{9}+7$.

------  Constraints ------
$1 ≤ k ≤ 100$
$2 ≤ n ≤ 3\cdot10^{5}$

------  Subtasks ------
Subtask 1 (20 points): $2 ≤ n ≤ 50$

Subtask 2 (80 points): original constraints

----- Sample Input 1 ------ 
5
5
----- Sample Output 1 ------ 
187500002
----- explanation 1 ------ 
Answer = $11/16 = 11\cdot16^{-1} = 187500002$

Difficulty: MEDIUM_HARD
Tags: Geometry

Mathematics

Probability

Starter code:

Solutions:
import math
n = int(input())
k = int(input())
if n == 1 or n == 2:
	print(0)
else:
	(num, denom) = (pow(2, n - 1) - n, pow(2, n - 1))
	m = 10 ** 9 + 7
	print(pow(denom, m - 2, m) * num % m)


def equilibrium(k, n):
	if k in [1, 2]:
		return 0
	else:
		(up, down, m) = (pow(2, k - 1) - k, pow(2, k - 1), 10 ** 9 + 7)
		return up * pow(down, m - 2, m) % m
k = int(input())
n = int(input())
print(equilibrium(k, n))


import math
P = int(input())
Q = int(input())
if P == 1 or P == 2:
	print(0)
else:
	(num, denom) = (pow(2, P - 1) - P, pow(2, P - 1))
	m = 10 ** 9 + 7
	print(pow(denom, m - 2, m) * num % m)


import math
nin = int(input())
k = int(input())
if nin == 1 or nin == 2:
	print(0)
else:
	(num, deno) = (pow(2, nin - 1) - nin, pow(2, nin - 1))
	mod = 10 ** 9 + 7
	print(pow(deno, mod - 2, mod) * num % mod)


try:
	import math
	n = int(input())
	k = int(input())
	if n == 1 or n == 2:
		print(0)
	else:
		num = pow(2, n - 1) - n
		denom = pow(2, n - 1)
		MOD = 10 ** 9 + 7
		print(pow(denom, MOD - 2, MOD) * num % MOD)
except:
	pass


mod = 10 ** 9 + 7
n = int(input())
k = int(input())
den = pow(2, n - 1)
num = pow(2, n - 1) - n
ans = pow(den, mod - 2, mod) * num % mod
print(ans)


try:
	n = int(input())
	k = int(input())
	mod = 1000000000 + 7

	def pow(a, b, mod):
		if b == 0:
			return 1
		ans = pow(a, b // 2, mod)
		ans = ans * ans % mod
		if b % 2 == 1:
			ans = a * ans % mod
		return ans
	den = pow(2, n - 1, mod)
	num = den - n
	if num < 0:
		num += mod
	iden = pow(den, mod - 2, mod)
	print(num * iden % mod)
except Exception:
	pass


from fractions import Fraction
n = int(input())
k = int(input())
if n == 1 or n == 2:
	print(0)
else:
	win = Fraction(pow(2, n - 1) - n, pow(2, n - 1))
	(num, denom) = (win.numerator, win.denominator)
	MOD = 10 ** 9 + 7
	print(pow(denom, MOD - 2, MOD) * num % MOD)


def modInverse():
	import math
	n = int(input())
	k = int(input())
	if n == 1 or n == 2:
		print('0')
	else:
		(num, denom) = (pow(2, n - 1) - n, pow(2, n - 1))
		MOD = 10 ** 9 + 7
		print(pow(denom, MOD - 2, MOD) * num % MOD)
modInverse()


def inp():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
MOD = 10 ** 9 + 7
n = inp()
inp()

def inv(x):
	return pow(x, MOD - 2, MOD)
ans = (1 - n * inv(pow(2, n - 1, MOD))) % MOD
print(ans)


from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *
from heapq import *
import operator
import math
from fractions import gcd
from random import randint

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
MOD = 10 ** 9 + 7
n = read()
read()

def inv(x):
	return pow(x, MOD - 2, MOD)
ans = (1 - n * inv(pow(2, n - 1, MOD))) % MOD
print(ans)


def extended_euclid(a, b):
	assert a > 0
	assert b > 0
	(x1, y1, m) = (1, 0, a)
	(x2, y2, n) = (0, 1, b)
	while m % n != 0:
		q = m // n
		(x1, y1, m, x2, y2, n) = (x2, y2, n, x1 - q * x2, y1 - q * y2, m - q * n)
	return (x2, y2, n)
mod = 10 ** 9 + 7
n = int(input())
k = int(input())
Q = 2 ** (n - 1)
P = Q - n
(x, y, n) = extended_euclid(Q, mod)
print((P * x + mod) % mod)


mod = 1000000007

def d(p):
	if p == 0:
		return 1
	if p == 1:
		return 2
	r = 1
	dhalf = d(p >> 1)
	if p % 2:
		r = 2
	return dhalf * dhalf * r % mod
n = int(input())
k = int(input())
ans = (d(n - 1) - n) % mod
ans *= d(mod - n)
ans %= mod
print(ans)


n = int(input())
k = int(input())
mod = 1000000000 + 7

def pow(a, b, mod):
	if b == 0:
		return 1
	ans = pow(a, b // 2, mod)
	ans = ans * ans % mod
	if b % 2 == 1:
		ans = a * ans % mod
	return ans
den = pow(2, n - 1, mod)
num = den - n
if num < 0:
	num += mod
iden = pow(den, mod - 2, mod)
print(num * iden % mod)


m = 1000000007

def power(a, b, m):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b = b >> 1
	return res

def solve(n):
	dnum = 1 << n - 1
	num = dnum - n
	return num * power(dnum, m - 2, m) % m
n = int(input())
k = int(input())
print(solve(n))


n = eval(input())
k = eval(input())

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m
if n < 500:
	if n == 2:
		print(0)
	elif n == 1:
		if k == 0:
			print(1)
		else:
			print(0)
	else:
		var3 = pow(2, n - 1)
		var2 = var3 - n
		var3 = power(var3, 1000000005, 1000000007)
		print(var2 * var3 % 1000000007)
else:
	var3 = pow(2, n - 1)
	var2 = var3 - n
	var3 = power(var3, 1000000005, 1000000007)
	print(var2 * var3 % 1000000007)


import math
from fractions import gcd
n = int(input())
j = int(input())
P = pow(2, n - 1) - n
Q = pow(2, n - 1)
while gcd(P, Q) != 1:
	hh = gcd(P, Q)
	P = P // hh
	Q = Q // hh
k = pow(10, 9) + 7
kk = pow(Q, k - 2, k)
ans = P * kk % k
print(ans)


def modInverse(a, m):
	return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m
n = int(input())
k = int(input())
nume = pow(2, n - 1) - n
deno = pow(2, n - 1)
modulo = modInverse(deno, 1000000007)
ans = nume * modulo % 1000000007
print(ans)


N = int(input())
k = int(input())

def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		print("Inverse doesn't exist")
	else:
		return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
P = 2 ** (N - 1) - N
Q = 2 ** (N - 1)
a = gcd(P, Q)
P = P // a
Q = Q // a
Qinv = modInverse(Q, 1000000007)
ans = Qinv * P % 1000000007
print(ans)


def invert(num, mod):
	X = 1
	Y = 0
	mcurr = mod
	flag = 0
	if mod == 1:
		flag = 1
		return 0
	while num > 1:
		flag = 0
		q = num // mod
		temp = mod
		mod = num % mod
		num = temp
		temp = Y
		flag = 2
		Y = X - q * Y
		X = temp
	if X < 0:
		flag = 1
		X = X + mcurr
	return X
n = int(input())
k = int(input())
p = pow(2, n - 1) - n
q = pow(2, n - 1)
ans = p * invert(q, 1000000007) % 1000000007
print(ans)


import math

def q(x, y, m):
	if m > 0:
		if y == 0:
			return 1
		p = q(x, y // 2, m) % m
		if y == 0:
			x += 1
		p = p * p % m
		if y % 2 == 0:
			return p
		z = x * p % m
		return z
	return m
n = int(input())
k = int(input())
b = 2 ** (n - 1) - n
m = 1000000007
a = 2 ** (n - 1)
x = q(a, m - 2, m)
if m > 0:
	ans = b * x % m
	print(int(ans))


def extended_gcd(aa, bb):
	(lastremainder, remainder) = (abs(aa), abs(bb))
	(x, lastx, y, lasty) = (0, 1, 1, 0)
	while remainder:
		(lastremainder, (quotient, remainder)) = (remainder, divmod(lastremainder, remainder))
		(x, lastx) = (lastx - quotient * x, x)
		(y, lasty) = (lasty - quotient * y, y)
	return (lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1))

def modinv(a, m):
	(g, x, y) = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m
n = int(input())
k = int(input())
div = pow(10, 9) + 7
p = 1
tot = 1
for _ in range(n - 1):
	p = p * 2 % div
	tot = tot * 2 % div
p = p - n
res = p * modinv(tot, div) % div
print(res)


n = int(input())
k = int(input())
mod = 10 ** 9 + 7
modinv = pow(2 ** (n - 1), mod - 2, mod)
print((2 ** (n - 1) - n) * modinv % mod)


def modInverse(a, m):
	g = gcd(a, m)
	return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
n = int(input())
k = int(input())
a = 2 ** (n - 1) - n
b = 2 ** (n - 1)
m = 1000000007
ans = modInverse(b, m)
ans = ans * a % m
print(ans)


n = int(input())
k = input()
a = n - 1
p = 1
while a > 0:
	p = p << 1
	a = a - 1
q = p
p = p - n
p = p % 1000000007
q_inv = pow(q, 1000000005, 1000000007)
ans = p * q_inv
ans = ans % 1000000007
print(ans)


def fastp(x, n, m):
	if n == 0:
		return 1
	elif n % 2 == 0:
		v = fastp(x, n / 2, m)
		return v * v % m
	else:
		v = fastp(x, n / 2, m)
		return x * v % m

def po(x, y, m):
	if y == 0:
		return 1
	t = y // 2
	peri = po(x, t, m)
	peri = peri % m
	peri = peri * peri % m
	if y % 2 == 0:
		return peri
	else:
		return x * peri % m

def gcd(a, c):
	if a == 0:
		return c
	return gcd(c % a, a)
a = int(input())
k = int(input())
n = 2 ** (a - 1)
m = 10 ** 9 + 7
r = gcd(n, m)
u = po(n, m - 2, m)
l = u * (n - a)
print(l % (10 ** 9 + 7))


m = 1000000007
n = int(input())
k = int(input())
p = pow(2, n - 1) - n
q = pow(2, n - 1)
q_inv = pow(q, m - 2, m)
res = p * q_inv % m
print(res)


def HCF(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def modI(a, m):
	mini = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		r = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - r * y
		x = t
	if x < 0:
		x = x + mini
	return x
n = int(input(''))
k = int(input(''))
p = 2 ** (n - 1) - n
q = 2 ** (n - 1)
w = HCF(p, q)
p = p // w
q = q // w
mh = modI(q, 1000000007)
kl = mh * p % 1000000007
print(kl)


def inverse(num, mod):
	o = mod
	p = 0
	q = 1
	if mod == 1:
		return 0
	while num > 1:
		quo = num // mod
		temp = mod
		mod = num % mod
		num = temp
		temp = p
		p = q - quo * p
		q = temp
	if q < 0:
		q = q + o
	return q
n = int(input())
k = int(input())
a = pow(2, n - 1)
P = a - n
Q = a
Q = inverse(Q, 1000000007)
print(P * Q % 1000000007)


def ans(num, denom):
	h = pow(10, 9) + 7
	inv = pow(denom, h - 2, h)
	ans = num * inv
	print(ans % h)
from fractions import gcd
n = int(input())
s = int(input())
a = pow(2, n - 1) - n
b = pow(2, n - 1)
check = 1
while check == 1:
	q = gcd(a, b)
	if q == 1:
		break
	else:
		a = a // q
		b = b // q
ans(a, b)


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
n = int(input())
tempN = n - 1
k = int(input())
while n % 2 == 0:
	n /= 2
	tempN -= 1
inv = modinv(2 ** tempN, 1000000007)
print(int((1 - n * inv) % 1000000007))


n = int(input())
k = int(input())

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
p = 2 ** (n - 1) - n
q = 2 ** (n - 1)
p = int(p)
mo = 1000000007
qinv = modInverse(q, mo)
print(p * qinv % 1000000007)


mod = 1000000007

def power(a, b):
	if b == 0:
		return 1
	temp = power(a, b // 2)
	if b % 2 == 0:
		return temp * temp % mod
	else:
		return a * (temp * temp) % mod % mod
n = int(input())
k = int(input())
k = n
x = 0
while n % 2 == 0:
	n = n // 2
	x = x + 1
den = power(2, k - 1 - x)
num = den - n
print(num * power(den, mod - 2) % mod)


x = int(input())
y = int(input())
m = 1000000007
ex = pow(2, x - 1)
eu = ex - x
ey = pow(ex, m - 2, m)
ez = eu * ey % m
print(ez)


(n, k) = (int(input()), int(input()))
q = 2 ** (n - 1)
p = q - n
res = pow(q, 1000000005, 1000000007)
print(p * res % 1000000007)


MOD = int(1000000000.0 + 7)

def mmi(x):
	return pow(x, MOD - 2, MOD)
n = int(input())
_ = int(input())
num = (pow(2, n - 1, MOD) - n) % MOD
denom = pow(2, n - 1, MOD)
ret = num * mmi(denom)
print(ret % MOD)


def fast_exp(x, y, _MOD):
	if y == 0:
		return 1
	p = fast_exp(x, y // 2, _MOD) % _MOD
	p = p * p % _MOD
	if y % 2 == 0:
		return p
	else:
		return x * p % _MOD
n = int(input())
k = int(input())
q = 2 ** (n - 1)
p = q - n
_MOD = 1000000007
print(p * fast_exp(q, _MOD - 2, _MOD) % _MOD)


def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
n = int(input())
k = int(input())
q = 2 ** (n - 1)
r = (q - n + 1000000007 + 1000000007 + 1000000007) % 1000000007
x = modInverse(q, 1000000007) % 1000000007
x = r * x % 1000000007
print(x)


M = 10 ** 9 + 7

def mod(e):
	if e > 30:
		return mod(e // 2) * mod(e - e // 2) % M
	return 2 ** e % M

def modinv(n):
	g = M + 1
	for i in range(n):
		if g % 2 != 0:
			g += M
		g //= 2
	return g
n = int(input())
k = int(input())
m = mod(n - 1)
q = 0
m = (m - n) % M
print(m * modinv(n - 1) % M)


from fractions import Fraction

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	return x % m

def calc(n, m):
	if n != 2:
		c = 1 << n - 1
		frac = Fraction(c - n, c)
		return frac.numerator * modinv(frac.denominator, m) % m
	else:
		return 0
m = 10 ** 9 + 7
n = int(input())
k = input()
print(calc(n, m))


def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def modInverse(a, m):
	return power(a, m - 2, m)
MOD = 1000000007
n = int(input())
k = int(input())
N = power(2, n - 1, MOD)
n = modInverse(N, MOD) * (N - n) % MOD
print(n)


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
p = 1000000007
n = int(input())
k = int(input())
s = power(2, n - 1, p)
c = power(s, p - 2, p)
ans = (s - n) * c % p
print(ans)


def modInverse(a, m):
	return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
n = int(input())
k = int(input())
q = 2 ** (n - 1)
p = q - n
r = modInverse(q, 1000000007)
print(p * r % 1000000007)


M = 1000000007

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def power(x, y):
	if y == 0:
		return 1
	pow = power(x, int(y / 2)) % M
	pow = pow * pow % M
	if y % 2 == 0:
		return pow
	else:
		return x * pow % M
n = input().split(' ')
n = int(n[0])
k = input().split(' ')
k = int(k[0])
q = power(2, n - 1)
p = q - n
x = gcd(p, q)
p = int(p / x)
q = int(q / x)
q = power(q, M - 2)
print(p % M * (q % M) % M)


import sys
f = sys.stdin
n = int(f.readline())
k = int(f.readline())
mod = int(1000000000.0 + 7)
q = pow(2, n - 1)
qinv = pow(q, mod - 2, mod)
p = q - n
print(p * qinv % mod)


MOD = 1000000007

def fastexp(a, b):
	res = 1
	while b > 0:
		if b % 2 == 1:
			res = res * a % MOD
		a = a * a % MOD
		b = b // 2
	return res

def modinv(a):
	return fastexp(a, MOD - 2)
N = int(input())
K = int(input())
Q = fastexp(2, N - 1)
P = Q - N
res = P * modinv(Q) % MOD
print(res)


def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
MOD = 10 ** 9 + 7
n = int(input())
k = int(input())
if n == 2:
	print(0)
else:
	Q = 2 ** (n - 1)
	P = 2 ** (n - 1) - n
	inverse = modInverse(Q, MOD)
	prod = P * inverse % MOD
	print(prod)


n = int(input())
print((pow(2, n - 1, 1000000007) + 1000000007 - n) % 1000000007 * pow(2, (n - 1) * 1000000005 % 1000000006, 1000000007) % 1000000007)


def exponential(a, b):
	a %= modulo
	sol = 1
	while b >= 1:
		if 1 & b:
			sol *= a
			sol %= modulo
		a = pow(a, 2) % modulo
		b >>= 1
	return sol
N = int(input())
K = int(input())
modulo = pow(10, 9) + 7
X = exponential(2, N - 1)
Y = exponential(X, modulo - 2)
Z = Y * (X - N) % modulo
print(Z % modulo)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def inverse_mod(a, m):
	g = gcd(a, m)
	return power(a, m - 2, m)
n = int(input())
k = int(input())
q = 2 ** (n - 1)
p = 2 ** (n - 1) - n
m = 1000000007
print(inverse_mod(q, m) * p % m)


import math

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
n = int(input())
k = int(input())
q = 2 ** (n - 1)
p = q - n
d = int(math.pow(10, 9) + 7)
print(p * modInverse(q, d) % d)


mod = 1000000007
num = int(input())
p = int(input())
number = 2 ** (num - 1)
inv = pow(number, mod - 2, mod)
print((number - num) * inv % mod)


n = int(input())
k = int(input())
m = 10 ** 9 + 7
zz = 2 ** (n - 1)
print((zz - n) * pow(zz, m - 2, m) % m)


import math

def modInverse(a, m):
	g = math.gcd(a, m)
	if g != 1:
		return 0
	else:
		return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m
n = int(input())
k = int(input())
q = 2 ** (n - 1)
p = q - n
f = math.gcd(p, q)
p = p // f
q = q // f
print(p * modInverse(q, 1000000007) % 1000000007)


n = int(input())
s = int(input())
p = 2 ** (n - 1)
p = p - n
q = 2 ** n
q = q // 2
m = 1000000000
m = m + 7

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m)
	p = p % m
	p = p ** 2
	p = p % m
	if y % 2 != 0:
		a = x * p
		a = a % m
		return a
	else:
		a = p
		return a

def modd(a, b, c):
	return a * b % c
A = power(q, m - 2, m)
print(modd(A, p, m))


def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def GCD(a, b):
	if b == 0:
		return a
	else:
		return GCD(b, a % b)
N = int(input())
K = int(input())
Num = 2 ** (N - 1) - N
Den = 2 ** (N - 1)
GCD = GCD(Den, Num)
Num = Num // GCD
Den = Den // GCD
Mod = 1000000007
print(Num % Mod * (modInverse(Den, Mod) % Mod) % Mod)


def modInverse(a, m):
	return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m
n = int(input())
k = int(input())
mod = 1000000007
q = 2 ** (n - 1)
p = q - n
qInv = modInverse(q, mod)
ans = p % mod * (qInv % mod) % mod
print(ans)


import math
n = int(input())
k = int(input())
q = int(pow(2, n - 1))
p = q - n
while math.gcd(p, q) > 1:
	r = math.gcd(p, q)
	p = p // r
	q = q // r
g = 1
h = 0
m = 1000000007
l = m
while q > 1:
	s = q // m
	n = m
	m = q % m
	q = n
	n = h
	h = g - s * h
	g = n
	if g < 0:
		g = g + l
print(p * g % 1000000007)


from fractions import Fraction
from math import gcd

def inverse(a, n):
	t = 0
	newt = 1
	r = n
	newr = a
	while newr != 0:
		quotient = r // newr
		(t, newt) = (newt, t - quotient * newt)
		(r, newr) = (newr, r - quotient * newr)
	if r > 1:
		return 0
	if t < 0:
		t += n
	return t

def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		return 0
	else:
		return pow(a, m - 2, m)

def reach_equilibrium():
	mod = 10 ** 9 + 7
	num_of_vectors = int(input())
	k = int(input())
	if num_of_vectors == 2:
		return 0
	return mod - num_of_vectors * modInverse(pow(2, num_of_vectors - 1), mod) % mod + 1
print(reach_equilibrium())


def modInverse(a, m):
	g = gcd(a, m)
	if g == 1:
		z = power(a, m - 2, m)
		t = b * z % m
		print(t)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
n = int(input())
x = int(input())
m = 1000000007
a = 2 ** (n - 1)
b = 2 ** (n - 1) - n
modInverse(a, m)


def modInverse(a, m, zz):
	if zz:
		g = gcd(a, m, True)
		if g != 1:
			return 0
		else:
			return power(a, m - 2, m, True)

def power(x, y, m, flag):
	if flag:
		if y == 0:
			return 1
		p = power(x, y // 2, m, True) % m
		p = p * p % m
		if y % 2 == 0:
			return p
		else:
			return x * p % m

def gcd(a, b, zz):
	if zz:
		if a == 0:
			return b
		return gcd(b % a, a, True)
N = int(input())
K = int(input())
if N == 2:
	print(0)
else:
	num = pow(2, N - 1, 1000000007) - N
	den = pow(2, N - 1, 1000000007)
	mod = modInverse(den, 1000000007, True)
	zz = mod * num
	ans = zz % 1000000007
	print(ans)


def modInv(a):
	m = 1000000007
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
n = int(input())
k = int(input())
q = 2 ** (n - 1)
p = q - n
d = modInv(q)
x = p * d % 1000000007
print(x)


p = 10 ** 9 + 7
n = int(input())
_ = input()
k = pow(2, n - 1)
print((k - n) * pow(k, p - 2, p) % p)


m = 1000000007
n = int(input())
k = int(input())
deno = 2 ** (n - 1)
nume = deno - n
deno = int(pow(deno, m - 2, m))
nume = nume % m * deno % m % m
print(nume)


import math
from sys import exit
from decimal import Decimal as dec

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

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

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

def main():
	n = nu()
	uselessfellow = nu()
	print((pow(2, n - 1, 1000000007) - n) * modInverse(pow(2, n - 1, 1000000007), 1000000007) % 1000000007)

def nu():
	return int(input())
main()


from fractions import Fraction as f
p = 10 ** 9 + 7
n = int(input())
_ = input()
k = pow(2, n - 1)
a = f(k - n, k)
print(a.numerator * pow(a.denominator, p - 2, p) % p)


from math import gcd
MOD = 1000000007
n = int(input())
k = int(input())
q = pow(2, n - 1)
p = q - n
qinv = pow(q, MOD - 2, MOD)
print(p % MOD * (qinv % MOD) % MOD)


from math import gcd

def mod(a, n, m):
	r = 1
	while n > 0:
		if n % 2 == 1:
			r = int(r * a % m)
		a = int(a * a % m)
		n = int(n / 2)
	return r
n = int(input())
k = int(input())
num = int(pow(2, n - 1) - n)
den = int(pow(2, n - 1))
g = gcd(num, den)
num = int(num // g)
den = int(den // g)
print(num * mod(den, 1000000005, 1000000007) % 1000000007)