Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef is playing a game against a magician. In this game, there are initially $N$ identical boxes in front of Chef and one of them contains a magic pill ― after eating this pill, you would never get compilation errors ever again.

Chef has to determine which box contains the pill. He is allowed to perform at most $M$ moves. In each move, Chef may do one of the following:
Choose one of the boxes that are in front of him uniformly randomly and guess that this box contains the pill. If the guess is correct, the game ends and Chef gets the pill. Otherwise, after this guess, the magician adds $K$ empty boxes in front of Chef in such a way that Chef cannot determine which boxes were added; the box Chef guessed also remains in front of him and Chef cannot distinguish this box from the other boxes in subsequent moves either.
Choose a number $X$ such that $X$ is a positive multiple of $K$, but strictly less than the current number of boxes in front of Chef. The magician then removes $X$ empty boxes. Of course, Chef must not perform this move if the current number of boxes is $≤ K$.

What is the probability that Chef gets the pill, assuming that he plays optimally ― in a way that maximises this probability? It can be proven that the maximum probability may be expressed as a fraction $P/Q$, where $P$ and $Q$ are coprime positive integers. You should compute $P \cdot Q^{-1}$ modulo $10^{9}+7$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $10^{9}+7$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains three space-separated integers $N$, $K$ and $M$.

------  Output ------
For each test case, print a single line containing one integer ― $P \cdot Q^{-1}$ modulo $10^{9}+7$, where $P/Q$ is the probability that Chef gets the pill.

------  Constraints  ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N < K ≤ 3 \cdot 10^{4}$
$1 ≤ M ≤ 3 \cdot 10^{4}$

------  Subtasks ------
Subtask #1 (20 points): 
$1 ≤ T ≤ 100$
$1 ≤ N < K ≤ 50$
$1 ≤ M ≤ 50$

Subtask #2 (20 points): 
$1 ≤ T ≤ 1,000$
$1 ≤ N < K ≤ 100$
$1 ≤ M ≤ 100$

Subtask #3 (60 points): original constraints

----- Sample Input 1 ------ 
3
5 9 1
7 9 2
3 20 3
----- Sample Output 1 ------ 
400000003
196428573
555555560
----- explanation 1 ------ 
Example case 1: Chef has only one move, so he should make a guess, which is correct with probability $1/5$. Note that if the guess was incorrect, there would be $14$ boxes in front of Chef afterwards.

Example case 2: In his first move, Chef should make a guess. With probability $1/7$, this guess is correct. With probability $6/7$, it is incorrect and there are $16$ boxes in front of Chef afterwards.

In his second move, Chef should again make a guess, which is correct with probability $1/16$. The probability that at least one of Chef's guesses was correct is $\frac{1}{7} + \frac{6}{7} \cdot \frac{1}{16} = 22/112 = 11/56$.

Example case 3: In the first move, Chef should make a guess, which is correct with probability $1/3$. In the second move, Chef should ask the magician to remove $X = 20$ boxes, leaving him with $3$ boxes again. In the third move, he should make a guess, which is again correct with probability $1/3$. The resulting probability is $5/9$.

Difficulty: HARD
Tags: Number theory

Mathematics

Probability

Starter code:

Solutions:
M = 10 ** 9 + 7
dp = {}

def MODmul(a, b):
	return a % M * (b % M) % M

def MODdiv(a, b):
	return a * pow(b, M - 2, M) % M

def MODdivFake(a, b):
	return (a, b)

def MODadd(a, b):
	return (a % M + b % M) % M

def MODsub(a, b):
	return (a % M - b % M + M) % M

def gcd(a, b):
	if (a, b) in dp:
		return dp[a, b]
	if a == 0:
		dp[a, b] = b
		return b
	dp[a, b] = gcd(b % a, a)
	return dp[a, b]

def gm(c, r, k):
	if c % 2:
		m = (c - 1) // 2
		rm_1 = pow(r - 1, m, M)
		rm = pow(r, m, M)
		n1 = MODmul(rm, r + k)
		n2 = rm_1 * (1 - r - k)
		d = MODmul(rm, r + k)
		return [MODadd(n1, n2), d]
	m = c // 2
	rm = pow(r, m, M)
	return [MODsub(rm, pow(r - 1, m, M)), rm]

def fracAdd(n1, d1, n2, d2):
	d1 = d1
	d2 = d2
	g = gcd(d1, d2)
	lcm = d1 * (d2 / g)
	n1 = n1 * (lcm // d1) % M
	n2 = n2 * (lcm // d2) % M
	n = (n1 + n2) % M
	return [int(n), int(lcm)]

def getFrac(n, k, c):
	if n == 1:
		return [1, 1]
	if c == 1:
		return [1, n]
	if n <= k:
		if c == 2:
			return [2 * n + k - 1, n * (n + k)]
		else:
			r = (n + k) % k
			if r == 0:
				r = n
			(n1, d1) = (1, n)
			(n2, d2) = (n - 1, n)
			(n3, d3) = gm(c - 1, r, k)
			n2 = MODmul(n2, n3)
			d2 = MODmul(d2, d3)
			return fracAdd(n1, d1, n2, d2)
	r = n % k
	if r == 1:
		return [1, 1]
	if r == 0:
		r = k
	return gm(c, r, k)

def ans(n, k, c):
	(n, d) = getFrac(n, k, c)
	g = gcd(n, d)
	(n, d) = [n // g, d // g]
	return MODdiv(n, d)
for _ in range(int(input())):
	(n, k, c) = map(int, input().split())
	print(ans(n, k, c))


import math
MOD = 1000000007

def multinv(x, mod):
	a = dev(x, mod)
	if a != 1:
		return 0
	else:
		return exp(x, mod - 2, mod)

def exp(a, b, mod):
	if b == 0:
		return 1
	m = exp(a, b // 2, mod) % mod
	m = m * m % mod
	if b % 2 == 0:
		return m
	else:
		return a * m % mod

def dev(m, n):
	if m == 0:
		return n
	return dev(n % m, m)
test = int(input())
for fu in range(test):
	(n, k, m) = map(int, input().split(' '))
	if m % 2 == 0:
		temp2 = exp(n, m // 2, MOD)
		temp4 = exp(n - 1, m // 2, MOD)
		p = (temp2 - temp4) * (n + k) % MOD + temp4
		q = temp2 * (n + k) % MOD
		q = multinv(q, MOD)
		res = p * q % MOD
	else:
		temp5 = exp(n, (m + 1) // 2, MOD)
		temp6 = exp(n - 1, (m + 1) // 2, MOD)
		p = (temp5 - temp6) % MOD
		q = multinv(temp5, MOD)
		res = p * q % MOD
	print(res)


md = 7 + pow(10, 9)

def StupidExponent(a, b):
	c = 1
	while b > 0:
		if b & 1:
			c = c * a % md
		b //= 2
		a = a * a % md
	return c

def StupidInverse(a):
	return StupidExponent(a, md - 2)
for z in range(int(input())):
	(n, k, m) = map(int, input().split())
	if m % 2:
		num = (StupidExponent(n, 1 + m // 2) - StupidExponent(n - 1, 1 + m // 2)) % md
		den = StupidExponent(n, 1 + m // 2)
	else:
		num = ((n + k) % md * StupidExponent(n, m // 2) % md - (n + k - 1) % md * StupidExponent(n - 1, m // 2) % md) % md
		den = (n + k) % md * StupidExponent(n, m // 2) % md
	print(num * StupidInverse(den) % md)


import math
N = 10 ** 9 + 7
a = int(input())
for i in range(a):
	(n, k, m) = [int(i) for i in input().split()]
	if m % 2 == 1:
		h = pow(n, (m + 1) // 2, N)
		t = pow(n, (m + 1) // 2, N) - pow(n - 1, (m + 1) // 2, N)
		gcd = math.gcd(h, t)
		h = h // gcd
		t = t // gcd
		print(pow(h, N - 2, N) * t % N)
	else:
		h = (n + k) * pow(n, m // 2, N) % N
		t = (n + k) * pow(n, m // 2, N) - (n + k - 1) * pow(n - 1, m // 2, N)
		gcd = math.gcd(h, t)
		h = h // gcd
		t = t // gcd
		print(pow(h, N - 2, N) * t % N)


import math
from fractions import Fraction
h = 10 ** 9 + 7

def modinv(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
for _ in range(int(input())):
	(n, k, m) = map(int, input().split())
	if m % 2 != 0:
		u = pow(n, (m + 1) // 2, h)
		v = (pow(n, (m + 1) // 2, h) - pow(n - 1, (m + 1) // 2, h)) % h
	else:
		u = pow(n, m // 2, h) * ((n + k) % h) % h
		v = (pow(n - 1, m // 2, h) * ((1 - n - k) % h) + pow(n, m // 2, h) * ((n + k) % h)) % h
	print(v * modinv(u, h) % h)


from math import floor

def modInverse(a, m):
	g = 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

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
la = 10 ** 9 + 7
t = int(input())
for i in range(t):
	(n, k, m) = map(int, input().split())
	if m % 2 == 1:
		x = floor(m / 2 + 1)
		a1 = power(n, x, la)
		b1 = power(n - 1, x, la)
		p1 = (a1 - b1) % la
		q1 = a1
		q2 = modInverse(q1, la)
		ans = p1 % la * (q2 % la) % la
		print(ans)
	else:
		x = m / 2
		k1 = power(n, x, la)
		part1 = (n + k) * k1 % la
		k2 = power(n - 1, x, la)
		part2 = k2 * (1 - (n + k)) % la
		p1 = (part1 + part2) % la
		q1 = part1
		q2 = modInverse(q1, la)
		ans = p1 * q2 % la
		print(ans)


mod = int(1000000000.0 + 7)

def expo(b, e):
	ans = 1
	while e:
		if e & 1:
			ans = ans * b % mod
			e -= 1
		else:
			b = b ** 2 % mod
			e = e >> 1
	return int(ans)
t = int(input())
while t:
	(n, k, m) = map(int, input().strip().split())
	if m & 1:
		den = expo(n, (m + 1) // 2)
		num = expo(n - 1, (m + 1) // 2)
		invden = expo(den, mod - 2) % mod
		ans = (den - num + mod) % mod * invden % mod
	else:
		den = expo(n, m // 2) * (k + n) % mod % mod
		num = expo(n - 1, m // 2) * ((k + n - 1) % mod) % mod
		invden = expo(den, mod - 2) % mod
		ans = (den - num + mod) % mod * invden % mod
	print(int(ans))
	t -= 1


def modulo(a, b, c):
	x = 1
	y = a
	while b > 0:
		if b & 1:
			x = x * y % c
		y = y * y % c
		b = b >> 1
	return x % c
mod = 10 ** 9 + 7
t = int(input())
for i in range(t):
	(n, k, m) = map(int, input().split())
	if m == 1:
		p = 1
		q = n
		ans = p * modulo(q, mod - 2, mod) % mod
	elif m == 2:
		p = n + n + k - 1
		q = n * (n + k)
		ans = p * modulo(q, mod - 2, mod) % mod
	else:
		z = (m + 1) // 2
		p = modulo(n, z, mod) - modulo(n - 1, z, mod)
		if p < 0:
			p += mod
		q = modulo(n, z, mod)
		ans = p * modulo(q, mod - 2, mod) % mod
		if m % 2 == 0:
			a = modulo(n - 1, z, mod)
			b = modulo(n, z, mod) * (n + k) % mod
			ans += a * modulo(b, mod - 2, mod) % mod
			ans %= mod
	print(ans)


import math
for t1 in range(int(input())):
	po = 10 ** 9 + 7
	(n, k, m) = map(int, input().split())
	if m % 2 == 0:
		d = m - 1
	else:
		d = m
	if m % 2 == 1:
		temp = int((m + 2) / 2)
		a1 = pow(n, temp, po)
		p1 = a1 - pow(n - 1, temp, po)
		q1 = a1 % po
	else:
		a1 = pow(n, m // 2, po)
		a2 = pow(n - 1, m // 2, po)
		a3 = n + k
		p1 = ((a1 - a2) * a3 + a2) % po
		q1 = a1 * a3 % po
	divi = math.gcd(p1, q1)
	p = p1 // divi
	q = q1 // divi
	print(pow(q, po - 2, po) * p % po)


import math

def modinverse(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
t = int(input())
while t > 0:
	t = t - 1
	mod = int(pow(10, 9)) + 7
	(n, k, m) = map(int, input().split())
	if m % 2 == 1:
		x = int((m + 1) // 2)
		a = pow(n, x, mod) - pow(n - 1, x, mod)
		b = pow(n, x, mod)
	else:
		x = int(m // 2)
		a = pow(n, x, mod) - pow(n - 1, x, mod)
		b = pow(n, x, mod)
		c = pow(n - 1, x, mod)
		d = pow(n, x, mod) * (n + k)
		a = a * d % mod + b * c % mod
		b = b * d
	x = math.gcd(a, b)
	a = int(a // x)
	b = int(b // x)
	b = modinverse(b)
	print(a * b % mod)


MOD = 1000000007

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

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

def GCD(a, b):
	if b == 0:
		return a
	return GCD(b, a % b)
testCase = int(input())
while testCase:
	testCase -= 1
	values = input()
	values = values.split(' ')
	values = list(map(int, values))
	n = values[0]
	k = values[1]
	m = values[2]
	if m % 2 != 0:
		term1 = power(n, (m + 1) // 2, MOD)
		term2 = power(n - 1, (m + 1) // 2, MOD)
		ans = term1 - term2
		GCD01 = GCD(ans, term1)
		ans //= GCD01
		term1 //= GCD01
		term3 = modinv(term1, MOD)
		print(ans * term3 % MOD)
	else:
		term1 = power(n, m // 2, MOD)
		term1 %= MOD
		term2 = power(n - 1, m // 2, MOD)
		term3 = term2
		term2 = term1 - term2
		term2 = term2 * (n + k)
		term2 += term3
		tErm4 = power(n, m // 2, MOD)
		term4 = tErm4 * (n + k)
		GCD01 = GCD(term2, term4)
		term2 //= GCD01
		term4 //= GCD01
		term4 = modinv(term4, MOD)
		print(term2 * term4 % MOD)


from fractions import Fraction
from math import ceil
p = 10 ** 9 + 7

def modinv(n, p):
	return pow(n, p - 2, p)

def get_ans(n, k, m):
	r = ceil(m / 2)
	top = pow(n, r, p) - pow(n - 1, r, p)
	top %= p
	if m % 2 == 0:
		top = top * (n + k) % p + pow(n - 1, r, p) % p
		top = top % p
		bottom = pow(n, r, p) * (n + k) % p
		f = Fraction(top, bottom)
		top = f.numerator
		bottom = f.denominator
		return top * pow(bottom, p - 2, p) % p
	else:
		bottom = pow(n, r, p)
		f = Fraction(top, bottom)
		top = f.numerator
		bottom = f.denominator
		return top * pow(bottom, p - 2, p) % p

def main():
	t = int(input())
	for i in range(t):
		x = input()
		(n, k, m) = [int(temp) for temp in x.split(' ')]
		print(get_ans(n, k, m))
	pass
main()


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 computeHCF(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def minimum(a, b):
	while 1:
		x = computeHCF(a, b)
		if x == 1:
			break
		a //= x
		b //= x
	return (a, b)
for _ in range(int(input())):
	(n, k, m) = map(int, input().split())
	a = 0
	b = 0
	if m == 1:
		print(modInverse(n, 1000000007) % 1000000007)
		continue
	tes = (m - 1) // 2 + 1
	nk = pow(n, tes, 1000000007)
	n1k = pow(n - 1, tes, 1000000007)
	a = nk - n1k
	b = nk
	if m % 2 == 0:
		a = a * (n + k) + n1k
		b = b * (n + k)
		a %= 1000000007
		b %= 1000000007
	(a, b) = minimum(a, b)
	print(a * modInverse(b, 1000000007) % 1000000007)


mod = 1000000007
from math import gcd

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:
		print(3 / 0)
	else:
		return x % m
t = int(input())
for i in range(t):
	lst = str(input()).split(' ')
	n = int(lst[0])
	k = int(lst[1])
	m = int(lst[2])
	if m % 2 == 0:
		j = m // 2
		q = pow(n, j, mod) * (n + k)
		p = q - pow(n - 1, j, mod) * (n + k - 1)
	else:
		j = (m + 1) // 2
		q = pow(n, j, mod)
		p = q - pow(n - 1, j, mod)
	g = gcd(p, q)
	p /= g
	q /= g
	p = int((p + mod) % mod)
	q = int((q + mod) % mod)
	print(int(p * modinv(q, mod)) % mod)


import math

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
t = int(input())
m = 1000000007
kl = m // 1000000007
for i in range(t):
	(n, k, mv) = map(int, input().split())
	nmv = (mv + 1) // 2
	if mv % 2 == 1:
		p = (power(n, nmv, m) - power(n - 1, nmv, m) + m) % m
		q = (power(n, nmv, m) + m) % m
	else:
		p = ((n + k) * (power(n, nmv, m) - power(n - 1, nmv, m)) + power(n - 1, nmv, m) + m) % m
		q = (power(n, nmv, m) * (n + k) + m) % m
	q = modInverse(q, m)
	ans = (p % m * (q % m) + m) % m
	print(ans)


def moduloInverse(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 isEven(x):
	if x % 2 == 0:
		return 1
	return 0
n = int(input())
mod = 1000000007
for i in range(n):
	list1 = list(map(int, input().split(' ')))
	if isEven(list1[2]) == 0:
		b = pow(list1[0], list1[2] // 2 + 1, mod) - pow(list1[0] - 1, list1[2] // 2 + 1, mod)
		b = b + 1000
		b = b - 1000
		c = pow(list1[0], list1[2] // 2 + 1, mod)
		c = c + 1000000
		c = c - 1000000
		if b < 0:
			b += mod
		print(b * moduloInverse(c, mod) % mod)
	elif isEven(list1[2]) == 1:
		a = list1[2] // 2
		b = pow(list1[0], a, mod) - pow(list1[0] - 1, a, mod)
		c = pow(list1[0], a, mod)
		if b < 0:
			b += mod
		d = moduloInverse(c, mod)
		print((moduloInverse(pow(list1[0], a, mod), mod) * pow(list1[0] - 1, a, mod) * moduloInverse((list1[0] + list1[1]) % mod, mod) + b * d % mod) % mod)


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

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

def modularExponentiation(a, b, divisor):
	res = 1
	a = a % divisor
	while b > 0:
		if b % 2 == 1:
			res = res * a % divisor
		b = b >> 1
		a = a * a % divisor
	return res
T = int(input())
for t in range(T):
	divisor = 1000000000 + 7
	(N, K, M) = list(map(int, input().split()))
	p = 1
	q = N
	if M % 2 == 1:
		power = M // 2 + 1
		temp = modularExponentiation(N, power, divisor)
		temp2 = modularExponentiation(N - 1, power, divisor)
		p = temp - temp2
		q = temp
	else:
		power = M // 2
		temp = modularExponentiation(N, power, divisor)
		temp2 = modularExponentiation(N - 1, power, divisor)
		p = (temp - temp2) * (N + K) + temp2
		q = temp * (N + K)
	qInverse = findInverseMod(q, divisor)
	print(p * qInverse % divisor)


def fpower(a, b):
	ans = 1
	while b > 0:
		if b & 1 == 1:
			ans = ans * a % 1000000007
		b = b >> 1
		a = a * a % 1000000007
	return ans

def gcd(m, n):
	if n == 0:
		return m
	return gcd(n, m % n)

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 += m0
	return x

def addfrac(m, n, o, p):
	a = gcd(n, p)
	num = (m * p // a + o * n // a) % 1000000007
	den = n * p // a % 1000000007
	return (int(num), int(den))
t = int(input())
while t > 0:
	(n, k, m) = map(int, input().split())
	if m % 2 != 0:
		num2 = fpower(n, m // 2 + 1) - fpower(n - 1, m // 2 + 1)
		den2 = fpower(n, m // 2 + 1)
		print(num2 * modinverse(den2, 1000000007) % 1000000007)
	else:
		num2 = fpower(n, m // 2) - fpower(n - 1, m // 2)
		den2 = fpower(n, m // 2)
		num3 = fpower(n - 1, m // 2)
		den3 = (n + k) * fpower(n, m // 2)
		(numerator, denominator) = addfrac(num2, den2, num3, den3)
		print(numerator * modinverse(denominator, 1000000007) % 1000000007)
	t = t - 1


import math

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

def power(x, y):
	p = 1000000007
	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
t = int(input())
for i in range(0, t):
	inp = input().split(' ')
	n = int(inp[0])
	k = int(inp[1])
	m = int(inp[2])
	if m % 2 == 0:
		t_p1 = power(n, m // 2)
		t_p2 = power(n - 1, m // 2)
		temp1 = (t_p1 - t_p2) % 1000000007 * (n + k) % 1000000007
		pro_x = (temp1 + t_p2) % 1000000007
		pro_y = t_p1 * (n + k) % 1000000007
		temp_gcd = math.gcd(pro_x, pro_y)
		temp_inv = modinv(temp_gcd, 1000000007)
		pro_x = pro_x * temp_inv % 1000000007
		pro_y = pro_y * temp_inv % 1000000007
	else:
		p1 = (m - 1) // 2 + 1
		temp_p = power(n, p1)
		pro_x = (temp_p - power(n - 1, p1)) % 1000000007
		pro_y = temp_p
		temp_gcd = math.gcd(pro_x, pro_y)
		temp_inv = modinv(temp_gcd, 1000000007)
		pro_x = pro_x * temp_inv % 1000000007
		pro_y = pro_y * temp_inv % 1000000007
	print(int(pro_x % 1000000007 * modinv(pro_y, 1000000007) % 1000000007))


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)
n = int(input())
for i in range(n):
	l1 = list(map(int, input().split(' ')))
	if l1[2] % 2 != 0:
		a = l1[2] // 2 + 1
		b = pow(l1[0], a, 1000000007) - pow(l1[0] - 1, a, 1000000007)
		c = pow(l1[0], a, 1000000007)
		if b < 0:
			b = b + 1000000007
		d = modInverse(c, 1000000007)
		print(b * d % 1000000007)
	elif l1[2] % 2 == 0:
		a = l1[2] // 2
		b = pow(l1[0], a, 1000000007) - pow(l1[0] - 1, a, 1000000007)
		c = pow(l1[0], a, 1000000007)
		if b < 0:
			b = b + 1000000007
		d = modInverse(c, 1000000007)
		e = b * d % 1000000007
		f = pow(l1[0], a, 1000000007)
		z = (l1[0] + l1[1]) % 1000000007
		g = modInverse(f, 1000000007)
		y = modInverse(z, 1000000007)
		h = pow(l1[0] - 1, a, 1000000007)
		print((g * h * y + e) % 1000000007)


import math
mod = 10 ** 9 + 7

def sumg(r, p, n):
	xp1 = pow(r, n, mod) - pow(p, n, mod)
	xp2 = pow(r, n, mod)
	return (xp1, xp2)

def f2(r, p, n):
	x2 = pow(r, n, mod)
	x1 = pow(p, n, mod)
	x2 = pow(x2, mod - 2, mod)
	rp = x1 * x2 % mod
	return rp
for i in range(int(input())):
	(n, k, m) = map(int, input().split())
	if m == 1:
		pm = pow(n, mod - 2, mod)
		print(pm)
	elif m % 2 == 1:
		rp = math.ceil(m / 2)
		(a, m) = sumg(n, n - 1, rp)
		mp = pow(m, mod - 2, mod)
		print(a * mp % mod)
	else:
		rp = math.ceil(m // 2)
		(a, m) = sumg(n, n - 1, rp)
		mp = pow(m, mod - 2, mod)
		sum1 = a * mp % mod
		xp = pow(n, rp, mod)
		xp1 = pow(n - 1, rp, mod)
		xp3 = pow(n + k, mod - 2, mod)
		xp = pow(xp, mod - 2, mod)
		ans = xp * xp1 * xp3 % mod
		print((sum1 + ans) % mod)


def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		return
	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)
t = int(input())
for i in range(t):
	(n, k, m) = map(int, input().split())
	r = 0
	if m % 2 != 0:
		p = power(n, m // 2 + 1, 1000000007) - power(n - 1, m // 2 + 1, 1000000007)
		p = p % 1000000007
		q = power(n, m // 2 + 1, 1000000007)
		q = modInverse(q, 1000000007)
		r = p % 1000000007 * (q % 1000000007) % 1000000007
	else:
		x = power(n, m // 2, 1000000007)
		x = x * (n + k) % 1000000007
		y = power(n - 1, m // 2, 1000000007)
		y = y * (1 - (n + k)) % 1000000007
		p = (x + y) % 1000000007
		q = power(n, m // 2, 1000000007)
		q = q * (n + k) % 1000000007
		q = modInverse(q, 1000000007)
		r = p * q % 1000000007
	print(r)


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

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 0:
		return 1
	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
t = int(input())
mod = 10 ** 9 + 7
while t > 0:
	t = t - 1
	(n, k, m) = map(int, input().split(' '))
	p = m // 2 + m % 2
	temp = pow(n - 1, p, mod)
	denom = pow(n, p, mod)
	num = (denom - temp) % mod
	if m % 2 == 0:
		nnum = temp
		ndenom = denom * (n + k) % mod
		num = (num * ndenom % mod + denom * nnum % mod) % mod
		denom = denom * ndenom % mod
	hcf = gcd(num, denom)
	num = num // hcf
	denom = denom // hcf
	print(int(num % mod * modInverse(denom, mod) % mod) % mod)


M = 10 ** 9 + 7

def po(x, y):
	res = 1
	x = x % M
	while y > 0:
		if int(y) & 1:
			res = res * x % M
		y = int(y / 2)
		x = x * x % M
	return res
for _ in range(int(input())):
	(n, k, m) = list(map(int, input().split()))
	if m == 1:
		deno = po(n, M - 2)
		print(deno)
		continue
	answer = 0
	if m % 2 != 0:
		m = int(m / 2)
		m += 1
		r = po(n, M - 2) * (n - 1) % M
		mul = po(n, M - 2)
		uhi = (1 - po(r, m) + M) % M
		uhi2 = (1 - r + M) % M
		uhi2 = po(uhi2, M - 2)
		uhi = uhi * uhi2 % M
		mul = mul * uhi % M
		print(mul)
	elif m % 2 == 0:
		m = m / 2
		r = po(n, M - 2) * (n - 1) % M
		mul = po(n, M - 2)
		uhi = (1 - po(r, m) + M) % M
		uhi2 = (1 - r + M) % M
		uhi2 = po(uhi2, M - 2)
		uhi = uhi * uhi2 % M
		mul = mul * uhi % M
		uhi3 = po(r, m)
		uhi4 = po(n + k, M - 2)
		uhi3 = uhi3 * uhi4 % M
		mul = (mul + uhi3) % M
		print(mul)


from fractions import Fraction

def ext_gcd(a, b):
	if a == 0:
		return (b, 0, 1)
	(d, x1, y1) = ext_gcd(b % a, a)
	x = y1 - b // a * x1
	y = x1
	return (d, x, y)

def inverse(a, m):
	(g, x, _) = ext_gcd(a, m)
	if g != 1:
		return
	return (x % m + m) % m
MOD = 10 ** 9 + 7

def pow(a, b, mod):
	res = 1
	x = a
	while b > 0:
		if b % 2 == 0:
			x = x * x % mod
			b //= 2
		else:
			res = res * x % mod
			b -= 1
	return res

def calc_fraction(a, b):
	p = a
	q = inverse(b, MOD)
	return p * q % MOD

def solve(n, k, m):
	n_mod = n % k
	f1 = Fraction(1, n)
	f2 = Fraction(1, n) + Fraction(n - 1, n) * Fraction(1, n + k)
	if n > k:
		f2 = max(f2, Fraction(1, n_mod))
	t = (m + 1) // 2 - 1
	f = f2 if m % 2 == 0 else f1
	(a, b) = (f.numerator, f.denominator)
	x = pow(n_mod - 1, t, MOD)
	y = pow(n_mod, t, MOD)
	numerator = (x * (a - b) % MOD + y * b % MOD) % MOD
	denominator = y * b % MOD
	return calc_fraction(numerator, denominator)
try:
	t = int(input())
except:
	pass
else:
	for _ in range(t):
		(n, k, m) = map(int, input().split())
		print(solve(n, k, m))


def fast_exp(num, power):
	result = 1
	while power > 0:
		if power % 2 == 1:
			result = result * num % 1000000007
		power = power // 2
		num = num * num % 1000000007
	return result

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
t = int(input())
for i in range(t):
	(n, k, m) = map(int, input().split(' '))
	e1 = fast_exp(n, (m + 1) // 2)
	e2 = fast_exp(n - 1, (m + 1) // 2)
	if m % 2 == 0:
		a2 = int(e1) * (n + k)
		a1 = (e1 - e2) * (n + k) + e2
	else:
		a1 = e1 - e2
		a2 = int(e1)
	nu = a1
	de = a2
	p = 10 ** 9 + 7
	q = nu * (modinv(de, p) % p) % p
	print(q)


MOD = 1000000007
dp = [0] * (100000 + 5)

def modularInverse(n, prime):
	dp[0] = dp[1] = 1
	for i in range(2, n + 1):
		dp[i] = dp[prime % i] * (prime - prime // i) % prime
modularInverse(100000, MOD)
t = int(input())

def power(x, y, p=MOD):
	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
while t > 0:
	t -= 1
	[n, k, m] = [int(i) for i in input().split()]
	if m == 1:
		print(dp[n])
	else:
		if n > k:
			if n % k == 0:
				n = k
			else:
				n = n - n // k * k
			m -= 1
		first = dp[n]
		second = dp[n + k]
		p = m // 2
		if m % 2 == 0:
			res = ((power(n, p) - power(n - 1, p)) % MOD * power(first, p) % MOD % MOD + power(n - 1, p) % MOD * power(first, p) % MOD * second % MOD % MOD) % MOD
		else:
			res = ((power(n, p) - power(n - 1, p)) % MOD * power(first, p) % MOD % MOD + power(n - 1, p) % MOD * power(first, p) % MOD * first % MOD % MOD) % MOD
		print(res % MOD)


import math

def modinv(a, pwr, modval):
	if pwr == 0:
		return 1
	p = modinv(a, pwr // 2, modval) % modval
	p = p * p % modval
	if pwr % 2 == 0:
		return p
	else:
		return a * p % modval
t = int(input())
for i in range(t):
	data = input().split(' ')
	n = int(data[0])
	k = int(data[1])
	m = int(data[2])
	cnt = n
	mod = 10 ** 9 + 7
	if m % 2 == 1:
		m = m // 2 + 1
		print((pow(n, m, mod) - pow(n - 1, m, mod)) % mod * modinv(n, mod - 1 - m, mod) % mod)
	else:
		p = m - 1
		p = p // 2 + 1
		val = (pow(n, p, mod) - pow(n - 1, p, mod)) % mod * modinv(n, mod - 1 - p, mod) % mod
		val2 = pow(n - 1, p, mod) * modinv(n, mod - 1 - p, mod) % mod * modinv(n + k, mod - 2, mod) % mod
		val = (val + val2) % mod
		print(val)


import math

def addfract(f1n, f1d, f2n, f2d):
	den = f1d * f2d
	num = f1n * f2d + f2n * f1d
	retval = math.gcd(min(num, den), max(num, den))
	num = num // retval
	den = den // retval
	return (num, den)

def modinv(a, pwr, modval):
	if pwr == 0:
		return 1
	p = modinv(a, pwr // 2, modval) % modval
	p = p * p % modval
	if pwr % 2 == 0:
		return p
	else:
		return a * p % modval
t = int(input())
for i in range(t):
	data = input().split(' ')
	n = int(data[0])
	k = int(data[1])
	m = int(data[2])
	cnt = n
	mod = 10 ** 9 + 7
	if m % 2 == 1:
		m = m // 2 + 1
		print((pow(n, m, mod) - pow(n - 1, m, mod)) % mod * modinv(n, mod - 1 - m, mod) % mod)
	else:
		p = m - 1
		p = p // 2 + 1
		val = (pow(n, p, mod) - pow(n - 1, p, mod)) % mod * modinv(n, mod - 1 - p, mod) % mod
		val2 = pow(n - 1, p, mod) * modinv(n, mod - 1 - p, mod) % mod * modinv(n + k, mod - 2, mod) % mod
		val = (val + val2) % mod
		print(val)


test = int(input())
while test > 0:
	(N, K, M) = map(int, input().split())
	p = int(1000000007)
	if M % 2 == 1:
		den = pow(N, (M + 1) // 2, p)
		num = den - pow(N - 1, (M + 1) // 2, p)
	else:
		den = pow(N, M // 2, p) * ((N + K) % p) % p
		num = (den - pow(N - 1, M // 2, p) * (N + K - 1) % p) % p
	modin = pow(den, p - 2, p)
	ans = modin * num % p
	print(ans)
	test -= 1


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

def fast_exp(num, power):
	result = 1
	while power > 0:
		if power % 2 == 1:
			result = result * num % 1000000007
		power = power // 2
		num = num * num % 1000000007
	return result

def gcd(aa, bb):
	if bb == 0:
		return aa
	else:
		return gcd(bb, aa % bb)
for i in range(int(input())):
	(n, k, p) = map(int, input().split())
	q = p // 2
	r = p % 2
	if r == 1:
		numf = fast_exp(n, q + 1) - fast_exp(n - 1, q + 1)
		denf = fast_exp(n, q + 1)
		t = gcd(numf, denf)
		numf = numf // t
		denf = denf // t
	else:
		numi = fast_exp(n, q) - fast_exp(n - 1, q)
		deni = fast_exp(n, q)
		numf = numi * (n + k) + (deni - numi)
		denf = deni * (n + k)
		t = gcd(numf, denf)
		numf = numf // t
		denf = denf // t
	h = 10 ** 9 + 7
	ll = modinv(denf, h)
	result = ll * numf % h
	print(result)


from fractions import Fraction

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

def minv(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
for i in range(int(input())):
	h = 10 ** 9 + 7
	[n, k, m] = map(int, input().split())
	if m == 1:
		p = 1
		q = n
		result = p % h * minv(q, h) % h
		print(result)
	elif m % 2 != 0:
		x = m // 2 + 1
		p = power(n, x, h) - power(n - 1, x, h)
		q = power(n, x, h)
		result = p % h * minv(q, h) % h
		print(result)
	else:
		x = m // 2
		p = (power(n, x, h) - power(n - 1, x, h)) * (n + k) + power(n - 1, x, h)
		q = power(n, x, h) * (n + k)
		result = p % h * minv(q, h) % h
		print(result)


import math

def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
from fractions import Fraction
t = int(input())
for i in range(t):
	(n, k, mi) = [int(x) for x in input().split()]
	mi = mi - 1
	num = n - 1
	den = n
	if mi % 2 == 1:
		num = num * pow(n - 1, mi // 2, 1000000007) * (n + k - 1)
		den = den * pow(n, mi // 2, 1000000007) * (n + k)
	else:
		num = num * pow(n - 1, mi // 2, 1000000007)
		den = den * pow(n, mi // 2, 1000000007)
	num = den - num
	gc = computeGCD(num, den)
	frac = Fraction(num, den)
	num = frac.numerator
	den = frac.denominator
	den = pow(den, 1000000005, 1000000007)
	print(num * den % 1000000007)


M = 1000000007

def modularExponentiation(x, n, M):
	if n == 0:
		return 1
	elif n % 2 == 0:
		return modularExponentiation(x * x % M, n // 2, M)
	else:
		return x * modularExponentiation(x * x % M, (n - 1) // 2, M) % M

def modInverse(A, M):
	return modularExponentiation(A, M - 2, M)

def power(a, b):
	if b == 0:
		return 1
	if b % 2 == 0:
		return power(a * a % M, b // 2) % M
	else:
		return a * power(a * a % M, (b - 1) // 2) % M
t = int(input())
mi = 100000
dp = [0] * (mi + 1)
dp[0] = dp[1] = 1
for i in range(2, mi + 1):
	dp[i] = dp[M % i] * (M - M // i) % M
while t > 0:
	t -= 1
	[n, k, m] = [int(i) for i in input().split()]
	if m == 1:
		print(dp[n])
	else:
		if n > k:
			if n % k == 0:
				n = k
			else:
				n = n - n // k * k
			m -= 1
		first = dp[n]
		second = dp[n + k]
		if m % 2 == 0:
			p = m // 2
			pfp = power(first, p)
			pnp = power(n - 1, p)
			res = (power(n, p) - pnp) * pfp % M + pnp * pfp * second % M
		else:
			p = m // 2
			pfp = power(first, p)
			pnp = power(n - 1, p)
			res = (power(n, p) - pnp) * pfp % M + pnp * pfp * first % M
		print(res % M)


MOD = 1000000007

def powerLL(x, n):
	result = 1
	while n:
		if n & 1:
			result = result * x % MOD
		n = int(n / 2)
		x = x * x % MOD
	return result

def powerStrings(sa, sb):
	a = 0
	b = 0
	for i in range(len(sa)):
		a = (a * 10 + (ord(sa[i]) - ord('0'))) % MOD
	for i in range(len(sb)):
		b = (b * 10 + (ord(sb[i]) - ord('0'))) % (MOD - 1)
	return powerLL(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
t = int(input())
for x in range(t):
	(n, k, m) = input().split()
	n = int(n)
	k = int(k)
	m = int(m)
	if m % 2 == 0:
		s1 = str(n)
		s2 = str(n - 1)
		ex = str(m // 2)
		a = powerStrings(s1, ex)
		b = powerStrings(s2, ex)
		num = ((a - b) * (n + k) % MOD + b % MOD) % MOD
		den = a * (n + k) % MOD
		minv = power(den, MOD - 2, MOD)
		ans = num * minv % MOD
	else:
		s1 = str(n)
		s2 = str(n - 1)
		ex = str((m + 1) // 2)
		a = powerStrings(s1, ex)
		b = powerStrings(s2, ex)
		num = a - b
		den = a
		minv = power(den, MOD - 2, MOD)
		ans = num * minv % MOD
	print(ans)


from fractions import Fraction
p = 1000000007

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for i in range(int(input())):
	(n, k, m) = map(int, input().split())
	if m & 1:
		m >>= 1
		m += 1
		denom = power(n, m, p)
		num = denom - power(n - 1, m, p)
		modInv = power(denom, p - 2, p)
		print(num % p * (modInv % p) % p)
	else:
		m >>= 1
		tmp_denom = power(n, m, p)
		tmp_num = power(n - 1, m, p)
		frac = Fraction(tmp_denom - tmp_num, tmp_denom) + (1 - Fraction(tmp_denom - tmp_num, tmp_denom)) * Fraction(1, n + k)
		num = frac.numerator
		modInv = power(frac.denominator, p - 2, p)
		print(num % p * (modInv % p) % p)


def modpow(a, n, modnum):
	result = 1
	while n > 0:
		if n & 1:
			result = result * a % modnum
		a = a * a % modnum
		n = n >> 1
	return result

def modinv(a, modnum):
	return modpow(a, modnum - 2, modnum)
modnum = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, k, m) = list(map(int, input().split()))
	r0 = modinv(n, modnum)
	r = modinv(n % k, modnum)
	nk = n % k % modnum
	if m % 2 == 1:
		m2 = (m - 1) // 2
		bunshi = (modpow(r, m2, modnum) * modpow(nk - 1, m2, modnum) - 1) % modnum
		inv = modinv(r * (nk - 1) - 1, modnum)
		ans = (r0 + r0 * (n - 1) * r * bunshi * inv) % modnum
	else:
		m2 = (m - 2) // 2
		bunshi = (modpow(r, m2, modnum) * modpow(nk - 1, m2, modnum) - 1) % modnum
		inv = modinv(r * (nk - 1) - 1, modnum)
		ans = (r0 + r0 * (n - 1) * r * bunshi * inv) % modnum
		ans = (ans + r0 * (n - 1) * modpow(r, m2, modnum) * modpow(nk - 1, m2, modnum) * modinv(nk + k, modnum)) % modnum
	print(ans)


M = 1000000007

def po(x, y):
	res = 1
	x = x % M
	while y > 0:
		if int(y) & 1:
			res = res * x % M
		y = int(y / 2)
		x = x * x % M
	return res
for _ in range(int(input())):
	(n, k, m) = list(map(int, input().split()))
	if m == 1:
		deno = po(n, M - 2)
		print(deno)
		continue
	answer = 0
	if n > k:
		value = int(n / k)
		value = value * k
		n -= value
		m -= 1
	if m % 2:
		m = int(m / 2)
		m += 1
		r = po(n, M - 2) * (n - 1) % M
		mul = po(n, M - 2)
		uhi = (1 - po(r, m) + M) % M
		uhi2 = (1 - r + M) % M
		uhi2 = po(uhi2, M - 2)
		uhi = uhi * uhi2 % M
		mul = mul * uhi % M
		print(mul)
	else:
		m = m / 2
		r = po(n, M - 2) * (n - 1) % M
		mul = po(n, M - 2)
		uhi = (1 - po(r, m) + M) % M
		uhi2 = (1 - r + M) % M
		uhi2 = po(uhi2, M - 2)
		uhi = uhi * uhi2 % M
		mul = mul * uhi % M
		uhi3 = po(r, m)
		uhi4 = po(n + k, M - 2)
		uhi3 = uhi3 * uhi4 % M
		mul = (mul + uhi3) % M
		print(mul)


M = 1000000007

def power(x, y):
	res = 1
	x = x % M
	while y > 0:
		if int(y) & 1:
			res = res * x % M
		y = int(y / 2)
		x = x * x % M
	return res
for _ in range(int(input())):
	(n, k, m) = list(map(int, input().split()))
	if m == 1:
		deno = power(n, M - 2)
		print(deno)
		continue
	ans = 0
	if n > k:
		val = int(n / k)
		val = val * k
		n -= val
		m -= 1
	if m % 2:
		m = int(m / 2)
		m += 1
		r = power(n, M - 2) * (n - 1) % M
		mul = power(n, M - 2)
		temp = (1 - power(r, m) + M) % M
		temp2 = (1 - r + M) % M
		temp2 = power(temp2, M - 2)
		temp = temp * temp2 % M
		mul = mul * temp % M
		print(mul)
	else:
		m = m / 2
		r = power(n, M - 2) * (n - 1) % M
		mul = power(n, M - 2)
		temp = (1 - power(r, m) + M) % M
		temp2 = (1 - r + M) % M
		temp2 = power(temp2, M - 2)
		temp = temp * temp2 % M
		mul = mul * temp % M
		temp3 = power(r, m)
		temp4 = power(n + k, M - 2)
		temp3 = temp3 * temp4 % M
		mul = (mul + temp3) % M
		print(mul)


from fractions import Fraction
for i in range(int(input())):
	(n, k, m) = map(int, input().split())
	if m % 2 == 1:
		a = pow(n, int(m / 2) + 1, 1000000007)
		b = a - pow(n - 1, int(m / 2) + 1, 1000000007)
		mdi = pow(a, 1000000005, 1000000007)
		print(b * mdi % 1000000007)
	else:
		a = pow(n, int(m / 2), 1000000007)
		b = pow(n - 1, int(m / 2), 1000000007)
		c = Fraction(a - b, a) + (1 - Fraction(a - b, a)) * Fraction(1, n + k)
		N = c.numerator
		denm = pow(c.denominator, 1000000005, 1000000007)
		print(N * denm % 1000000007)


from fractions import Fraction
for i in range(int(input())):
	(n, k, m) = map(int, input().split())
	if m % 2 == 1:
		mau = pow(n, int(m / 2) + 1, 1000000007)
		tu = mau - pow(n - 1, int(m / 2) + 1, 1000000007)
		maund = pow(mau, 1000000005, 1000000007)
		print(tu * maund % 1000000007)
	else:
		nx = pow(n, int(m / 2), 1000000007)
		n1x = pow(n - 1, int(m / 2), 1000000007)
		a = Fraction(nx - n1x, nx) + (1 - Fraction(nx - n1x, nx)) * Fraction(1, n + k)
		num = a.numerator
		dend = pow(a.denominator, 1000000005, 1000000007)
		print(num * dend % 1000000007)


import math
mod = 1000000007

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 fast_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
t = int(input())
while t > 0:
	(n, k, m) = map(int, input().split())
	ne = 0
	de = 0
	if m % 2 == 0:
		a = fast_power(n, int(m / 2), mod)
		b = fast_power(n - 1, int(m / 2), mod)
		ne = (a - b) * (n + k) + b
		de = a * (n + k)
	else:
		aa = fast_power(n, int(m / 2) + 1, mod)
		bb = fast_power(n - 1, int(m / 2) + 1, mod)
		ne = aa - bb
		de = aa
	hcf = math.gcd(ne, de)
	ne = ne / hcf
	de = de / hcf
	ans = int(int(ne) * int(modInverse(de, mod)) % mod)
	print(ans)
	t = t - 1


from fractions import Fraction
import math

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

def fun(n, k, m):
	b = Fraction(1, n + k)
	x = (m - 1) // 2 + 1
	y = (m - 2) // 2 + 1
	ans = 0
	if m & 1:
		c = pow(n - 1, x, 1000000007)
		d = pow(n, x, 1000000007)
		a = Fraction(c, d)
		ans = Fraction(1, 1) - a
	else:
		c = pow(n - 1, y, 1000000007)
		d = pow(n, y, 1000000007)
		a = Fraction(c, d)
		ans = Fraction(1, 1) - a + a * b
	ans = str(ans)
	if ans == '1':
		print(1)
	else:
		(a, b) = list(map(int, ans.split('/')))
		x = modInverse(b, 1000000007)
		print(a % 1000000007 * (x % 1000000007) % 1000000007)

def main():
	for _ in range(int(input())):
		(n, k, m) = list(map(int, input().split()))
		fun(n, k, m)
main()


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
import math
t = int(input())
mod = 10 ** 9 + 7
while t > 0:
	(n, k, m) = map(int, input().split())
	if m % 2 == 0:
		p = pow(n, int(m / 2), mod) * (n + k) % mod - pow(n - 1, int(m / 2), mod) * (n + k - 1) % mod
		q = pow(n, int(m / 2), mod) * (n + k) % mod
	else:
		p = pow(n, int(m / 2) + 1, mod) % mod - pow(n - 1, int(m / 2) + 1, mod) % mod
		q = pow(n, int(m / 2) + 1, mod) % mod
	ans = p * modInverse(q, mod) % mod
	print(ans)
	t = t - 1


import math
modulo = int(1000000007)

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 intpow(base, exp):
	if exp == 0:
		return 1
	elif exp == 1:
		return base
	elif exp & 1 != 0:
		return base * intpow(base * base % modulo, exp // 2) % modulo
	return intpow(base * base % modulo, exp // 2)
t = int(input())
for l in range(t):
	(n, k, m) = map(int, input().split())
	j = int(0)
	x = int(1)
	y = int(0)
	a = int(1)
	b = int(1)
	if n > k and n % k != 0:
		n = n % k
		m = m - 1
	elif n > k:
		n = k
		m = m - 1
	if m % 2 == 0:
		a = int(intpow(n, m // 2))
		b = int(intpow(n - 1, m // 2))
		y = int(a - b)
		x = int(a)
		y = y * (n + k) + b
		x = x * (n + k)
	elif m % 2 != 0:
		a = int(intpow(n, (m + 1) // 2))
		b = int(intpow(n - 1, (m + 1) // 2))
		y = int(a - b)
		x = int(a)
	x = int(x % modulo)
	y = int(y % modulo)
	z = y
	(g, x, y) = egcd(x, modulo)
	a = (x % modulo + modulo) % modulo
	k = z * a % modulo
	print(k)


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
for T in range(int(input())):
	value = 1000000007
	(N, K, M) = map(int, input().split())
	a = (N - 1) * modinverse(N, value)
	if M == 1:
		answer = modinverse(N, value)
	elif M == 2:
		answer = modinverse(N, value) + a * modinverse(N + K, value)
	elif M % 2 == 1:
		n = (M + 1) // 2
		b = power(a, n, value)
		answer = 1 - b
	else:
		n = M // 2
		b = power(a, n, value)
		d = 1 - b
		e = b * modinverse(N + K, value)
		answer = d + e
	print(answer % value)


from math import gcd
mod = 10 ** 9 + 7

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

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

def answer(p, q):
	x = gcd(p, q)
	p = p // x
	q = q // x
	return p % mod * (modInverse(q, mod) % mod) % mod
for i in range(int(input())):
	(n, k, m) = map(int, input().split())
	if m == 1:
		print(answer(1, n))
	else:
		if m % 2 == 0:
			x = m // 2
		else:
			x = (m + 1) // 2
		p = n - 1
		q = n
		num1 = power(q, x, mod) - power(p, x, mod)
		deno = power(q, x, mod)
		if m % 2 == 0:
			num1 = (power(q, x, mod) - power(p, x, mod)) * (n + k) + power(p, x, mod)
			deno = power(n, x, mod) * (n + k)
		print(answer(num1, deno))


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

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
	return x * p % m
MOD = 1000000007
for _ in range(int(input())):
	(n, k, m) = map(int, input().split())
	x = (m + 1) // 2
	p = power(n - 1, x, MOD)
	q = power(n, x, MOD)
	y = p * modInverse(q, MOD)
	result = 1 - y + MOD
	if m % 2 == 0:
		result += y * modInverse(n + k, MOD)
	print(result % MOD)


mod = 1000000007

def modular(x, n, mod):
	if n == 0:
		return 1
	elif n % 2 == 0:
		y = modular(x, n / 2, mod)
		return y % mod * (y % mod) % mod
	else:
		return x % mod * modular(x, n - 1, 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

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
while t:
	t = t - 1
	(n, k, m) = [int(x) for x in input().split()]
	if m % 2 != 0:
		x = int((m + 1) / 2)
		num = (modular(n, x, mod) % mod - modular(n - 1, x, mod) % mod + mod) % mod
		den = int(modular(n, x, mod))
	else:
		x = int(m / 2)
		num = int(((n + k) * ((modular(n, x, mod) % mod - modular(n - 1, x, mod) % mod + mod) % mod) + modular(n - 1, x, mod)) % mod)
		den = int((n + k) * modular(n, x, mod))
	y = gcd(num, den)
	num = num // y
	den = den // y
	ss = modInverse(den, mod)
	ans = num % mod * (ss % mod) % mod
	print(ans)


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

def lowest(den3, num3):
	common_factor = gcd(num3, den3)
	den3 = int(den3 / common_factor)
	num3 = int(num3 / common_factor)
	return (num3, den3)

def add_frac(num1, den1, num2, den2):
	den3 = gcd(den1, den2)
	den3 = den1 * den2 / den3
	num3 = num1 * (den3 / den1) + num2 * (den3 / den2)
	(num3, den3) = lowest(den3, num3)
	return (num3, den3)

def power(x, y, mod):
	if y == 0:
		return 1
	p = power(x, y // 2, mod) % mod
	p = p * p % mod
	return p if y % 2 == 0 else x * p % mod
modulus = 1000000007
for t in range(int(input())):
	l = input().split()
	n = int(l[0])
	k = int(l[1])
	m = int(l[2])
	if m % 2 == 0:
		terms = m // 2
		gp_n = power(n - 1, terms, modulus)
		gp_d = power(n, terms, modulus)
		n1 = gp_d - gp_n
		d2 = gp_d * (n + k)
		(n1, d1) = add_frac(n1, gp_d, gp_n, d2)
	else:
		terms = (m + 1) // 2
		gp_n = power(n - 1, terms, modulus)
		gp_d = power(n, terms, modulus)
		n1 = gp_d - gp_n
		d1 = gp_d
	print(n1 * power(d1, modulus - 2, modulus) % modulus)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k, m) = map(int, input().split())
	if n <= k:
		(a, b, val) = (n, n - 1, m // 2)
		if m % 2 != 0:
			ans = 1 - pow(b * pow(a, mod - 2, mod) % mod, val + 1, mod)
		else:
			ans = 1 - pow(b * pow(a, mod - 2, mod) % mod, val, mod) * (1 - pow(n + k, mod - 2, mod))
	else:
		(a, b, val) = (n - k * (n // k), n - k * (n // k) - 1, m // 2)
		if m % 2 == 0:
			ans = 1 - pow(b * pow(a, mod - 2, mod) % mod, val, mod)
		else:
			ans = 1 - pow(b * pow(a, mod - 2, mod) % mod, val, mod) * (1 - pow(a + k, mod - 2, mod))
	ans %= mod
	print(ans)


from math import gcd

def power(x, y):
	mo = 1000000007
	res = 1
	while y > 0:
		if y & 1 == 1:
			res = res % mo * (x % mo) % mo
		y = y >> 1
		x = x % mo * (x % mo) % mo
	return res

def mI(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
t = int(input())
while t:
	mm = 1000000007
	(n, k, m) = map(int, input().split())
	if m % 2 == 0:
		m = m // 2
		a = power(n - 1, m)
		c = a
		b = power(n, m)
		a = b - a
		d = b % mm * ((k + n) % mm) % mm
		a = a % mm * ((k + n) % mm) % mm + c
		b = d
	else:
		m = m // 2 + 1
		a = power(n - 1, m)
		b = power(n, m)
		a = b - a
	c = gcd(b, mm)
	b = b // c
	mm = mm // c
	an = mI(b, mm)
	re = a % mm * (an % mm) % mm
	print(re)
	t -= 1


import math
from sys import stdin, stdout
maxn = 1000000007
np = stdin.readline
for _ in range(int(np())):
	(n, k, m) = map(int, np().split())
	if m % 2 == 0:
		ch = m // 2
		num = pow(n - 1, ch, maxn) * (n + k - 1) % maxn
		den = pow(n, ch, maxn) * (n + k) % maxn
	else:
		ch = (m + 1) // 2
		num = pow(n - 1, ch, maxn) % maxn
		den = pow(n, ch, maxn) % maxn
	num = den - num
	print(num * pow(den, maxn - 2, maxn) % maxn)


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):
	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
t = int(input())
a = 1000000007
while t:
	t = t - 1
	(n, k, m) = map(int, input().split())
	if m % 2 == 1:
		p = power(n, m // 2 + 1, a) - power(n - 1, m // 2 + 1, a)
		q = power(n, m // 2 + 1, a)
	else:
		p = power(n, m // 2, a) * (n + k) - power(n - 1, m // 2, a) * (n + k - 1)
		q = power(n, m // 2, a) * (n + k)
	print(p * modInverse(q, a) % a)


h = 1000000007

def modin(n):
	(ri, rj) = (h, n)
	(ti, tj) = (0, 1)
	while rj != 0:
		q = ri // rj
		(ri, rj) = (rj, ri - q * rj)
		(ti, tj) = (tj, ti - q * tj)
	ans = ti % h
	if ans < 0:
		return ans + h
	else:
		return ans

def power(a, n):
	if n == 1:
		return a % h
	if n == 2:
		return a ** 2
	elif n == 3:
		return a ** 3
	if n % 2 == 0:
		b = power(a, n // 2)
		return b * b % h
	else:
		b = power(a, n // 2)
		return b * b * a % h

def solve(i):
	(n, k, c) = i
	if c == 1:
		return modin(n)
	if n % k == 1:
		return 1
	roll = 1 + (c - 1) // 2
	if c % 2 == 1:
		s = (1 - power((n - 1) * modin(n) % h, roll)) % h
	else:
		s = (1 - power((n - 1) * modin(n) % h, roll) % h * ((n + k - 1) * modin(n + k)) % h) % h
	return s
a = []
for _ in range(int(input())):
	a.append([int(x) for x in input().split()])
for i in a:
	print(solve(i))


import math

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)
t = int(input())
while t != 0:
	a = list(map(int, input().split()))
	n = a[0]
	del a[0]
	k = a[0]
	del a[0]
	m = a[0]
	del a[0]
	if m % 2 == 0:
		x = pow(int(n), int(m / 2), 10 ** 9 + 7)
		y = int(x)
		y *= int(n + k)
		y %= 10 ** 9 + 7
		x -= pow(int(n - 1), int(m / 2), 10 ** 9 + 7)
		x *= int(n + k)
		x %= 10 ** 9 + 7
		x += pow(int(n - 1), int(m / 2), 10 ** 9 + 7)
	else:
		x = pow(int(n), int((m + 1) / 2), 10 ** 9 + 7)
		y = int(x)
		x -= pow(int(n - 1), int((m + 1) / 2), 10 ** 9 + 7)
	x %= 1000000007
	y %= 1000000007
	print(int(x * modInverse(y, 1000000007)) % 1000000007)
	t -= 1


from math import *

def powww(x, y):
	val = 1
	mod = 1000000007
	while y != 0:
		if y & 1:
			val = val * x % mod
		x = x * x % mod
		y >>= 1
	return val

def solve(t):
	mod = 1000000007
	while t > 0:
		t -= 1
		(n, k, m) = input().split()
		n = int(n)
		m = int(m)
		k = int(k)
		if n <= 1:
			val = powww(1, mod - 2) % mod
		else:
			r1 = int(ceil(float(m + 1) / 2.0))
			if m & 1 == 0:
				n1 = powww(n, r1 - 1)
				n2 = powww(n - 1, r1 - 1)
				n3 = (n1 * (n + k) - (n + k) * n2 + n2) % mod
				d1 = powww(n, (r1 - 1) * (mod - 2))
				d2 = powww(n + k, mod - 2)
				d3 = d1 * d2 % mod
				val = n3 * d3 % mod
			else:
				n1 = powww(n, r1)
				n2 = powww(n - 1, r1)
				d1 = powww(n, r1 * (mod - 2))
				val = (n1 - n2) % mod * d1 % mod
		print(val)
t = int(input())
solve(t)


from fractions import Fraction as f
import sys
sys.setrecursionlimit(300002)

def mod(a):
	return (a % 1000000007 + 1000000007) % 1000000007

def power2(x, y):
	if y == 0:
		return 1
	elif int(y % 2) == 0:
		tmp = power2(x, int(y / 2))
		return mod(tmp * tmp)
	else:
		tmp = power2(x, int(y / 2))
		return mod(x * mod(tmp * tmp))

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 modInverse(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def Test():
	a = [int(i) for i in input().split(' ')]
	N = a[0]
	K = a[1]
	M = a[2]
	pp = power2(N, M / 2 + 1) - power2(N - 1, M / 2 + 1)
	qq = power2(N, M / 2 + 1)
	if M % 2 == 0:
		qq = (N + K) * power2(N, M / 2)
		pp = mod((power2(N, M / 2) - power2(N - 1, M / 2)) * (N + K))
		pp += power2(N - 1, M / 2)
	m = modInverse(qq, 1000000007)
	print(mod(pp * m))
T = int(input())
for i in range(0, T):
	Test()


import math
for _ in range(int(input())):
	(n, k, m) = map(int, input().split())
	if m % 2 != 0:
		ra = pow(n, m // 2 + 1, 10 ** 9 + 7) - pow(n - 1, m // 2 + 1, 10 ** 9 + 7)
		num = ra * n
		den = n * pow(n, m // 2 + 1, 10 ** 9 + 7)
		factor = math.gcd(num, den)
		tmp1 = num // factor
		tmp2 = den // factor
		mod = 10 ** 9 + 7
		g = math.gcd(tmp2, mod)
		if g == 1:
			print(tmp1 * pow(tmp2, mod - 2, mod) % mod)
		else:
			print(0)
	else:
		ra = pow(n, m // 2, 10 ** 9 + 7) - pow(n - 1, m // 2, 10 ** 9 + 7)
		num = ra * n
		den = n * pow(n, m // 2 + 1, 10 ** 9 + 7)
		nul = pow(n - 1, m // 2, 10 ** 9 + 7)
		dul = (n + k) * pow(n, m // 2, 10 ** 9 + 7)
		den = n * pow(n, m // 2, 10 ** 9 + 7)
		num = num * dul + nul * den
		den = dul * den
		factor = math.gcd(num, den)
		tmp1 = num // factor
		tmp2 = den // factor
		mod = 10 ** 9 + 7
		g = math.gcd(tmp2, mod)
		if g == 1:
			print(tmp1 * pow(tmp2, mod - 2, mod) % mod)
		else:
			print(0)


M = 10 ** 9 + 7
import math
for _ in range(int(input())):
	(n, k, m) = list(map(int, input().split()))
	if m == 1:
		print(pow(n, M - 2, M))
	else:
		if n > k:
			if n % k != 0:
				m -= 1
				n = n % k
				if m & 1:
					out = (1 - pow(n - 1, m // 2 + 1, M) * pow(pow(n, M - 2, M), m // 2 + 1, M) % M + M) % M
				else:
					inv = pow(n, M - 2, M)
					z = pow(n - 1, m // 2, M) * pow(inv, m // 2, M) % M
					out = (1 - z + M + z * pow(n + k, M - 2, M) % M + M) % M
			else:
				n = k
				m -= 1
				if m & 1:
					inv = pow(n, M - 2, M)
					out = (1 - pow(n - 1, m // 2 + 1, M) * pow(inv, m // 2 + 1, M) % M + M) % M
				else:
					inv = pow(n, M - 2, M)
					z = pow(n - 1, m // 2, M) * pow(inv, m // 2, M) % M
					out = (1 - z + M + z * pow(n + k, M - 2, M) % M + M) % M
		elif m & 1:
			inv = pow(n, M - 2, M)
			out = (1 - pow(n - 1, m // 2 + 1, M) * pow(inv, m // 2 + 1, M) % M + M) % M
		else:
			inv = pow(n, M - 2, M)
			z = pow(n - 1, m // 2, M) * pow(inv, m // 2, M) % M
			out = (1 - z + M + z * pow(n + k, M - 2, M) % M + M) % M
		print(out)


def modinve(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
t = int(input())
for i in range(t):
	(n, k, m) = list(map(int, input().strip().split()))
	if m % 2 == 0:
		p = (pow(n, m // 2, 10 ** 9 + 7) * (n + k) - pow(n - 1, m // 2, 10 ** 9 + 7) * (n + k) + pow(n - 1, m // 2, 10 ** 9 + 7)) % (10 ** 9 + 7)
		q = pow(n, m // 2, 10 ** 9 + 7) * (n + k) % (10 ** 9 + 7)
	else:
		p = (pow(n, (m + 1) // 2, 10 ** 9 + 7) - pow(n - 1, (m + 1) // 2, 10 ** 9 + 7)) % (10 ** 9 + 7)
		q = pow(n, (m + 1) // 2, 10 ** 9 + 7) % (10 ** 9 + 7)
	op = modinve(q % (10 ** 9 + 7), 10 ** 9 + 7) * p
	op = op % (10 ** 9 + 7)
	print(int(op))


tt = int(input())
mod = 1000000007
x = 1
if tt <= 1000:
	x = 0
for _ in range(tt):
	if x == 1:
		(N, k, m) = map(int, input().split(' '))
		res = pow(N, mod - 2, mod)
		if m % 2 == 1:
			n = m // 2 + 1
		else:
			n = m // 2
		y = pow(N, n, mod)
		y = pow(y, mod - 2, mod)
		s = pow(N, n, mod) - pow(N - 1, n, mod)
		s += mod * 1000
		s = s % mod
		s = s * y % mod
		if m == 2:
			temp = (N - 1) * pow(N, mod - 2, mod) * pow(N + k, mod - 2, mod)
			s += temp % mod
			s = s % temp
		elif m % 2 == 0:
			temp = pow(N, n, mod)
			s += pow(N - 1, n, mod) * pow(N + k, mod - 2, mod) * pow(temp, mod - 2, mod) % mod
			s = s % mod
		if m == 1:
			print(res)
		else:
			print(s % mod)
	else:
		(n, k, m) = map(int, input().split(' '))
		y = pow(n, mod - 2, mod)
		l1 = []
		l1.append(pow(n, mod - 2, mod))
		i = 1
		m = m - 1
		while m > 0:
			if m >= 2:
				x = pow(n - 1, 1, mod)
				x = x * y % mod
				l1.append(l1[i - 1] * x % mod)
				m = m - 2
				i += 1
			else:
				x = l1[i - 1] * n
				x *= n - 1
				x *= pow(n, mod - 2, mod)
				x = x % mod
				x = x * pow(1, 1, mod) % mod
				x *= pow(n + k, mod - 2, mod)
				x = x % mod
				l1.append(x)
				i = i + 1
				m = m - 1
		print(sum(l1) % mod)


import math
te = int(input())
for i in range(te):
	arr = list(map(int, input().split()))
	N = int(arr[0])
	K = int(arr[1])
	M = int(arr[2])
	pr = int(pow(10, 9) + 7)
	if M % 2 == 1:
		T = int((M + 1) // 2)
		Q = int(pow(N, T, pr))
		P = int(Q - pow(N - 1, T, pr))
	else:
		T = int(M // 2)
		Q = int(pow(N, T, pr) * (N + K))
		P = int(Q - (N + K - 1) * pow(N - 1, T, pr))
	p = int(pr - 2)
	print(P % pr * pow(Q, p, pr) % pr)


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)
MOD = 1000000007

def powerLL(x, n):
	result = 1
	while n:
		if n & 1:
			result = result * x % MOD
		n = int(n / 2)
		x = x * x % MOD
	return result

def powerStrings(sa, sb):
	a = 0
	b = 0
	for i in range(len(sa)):
		a = (a * 10 + (ord(sa[i]) - ord('0'))) % MOD
	for i in range(len(sb)):
		b = (b * 10 + (ord(sb[i]) - ord('0'))) % (MOD - 1)
	return powerLL(a, b)
T = int(input())
for M in range(T):
	(n, k, m) = input().split()
	n = int(n)
	k = int(k)
	m = int(m)
	n1 = str(n)
	n2 = str(n - 1)
	if m % 2 != 0:
		x = (m + 1) // 2
		x1 = str(x)
		a = powerStrings(n1, x1)
		b = powerStrings(n2, x1)
		P = a - b
		Q = a
	else:
		x = m // 2
		x1 = str(x)
		a = powerStrings(n1, x1)
		b = powerStrings(n2, x1)
		P = (n + k) * (a - b) + b
		Q = a * (n + k)
	m = 1000000007
	mi = power(Q, m - 2, m)
	print(P * mi % m)


mod = 1000000007

def mcounter(M, counter):
	if M % 2 == 0:
		m = M // 2
		counter = 1
	else:
		m = (M + 1) // 2
	return (m, counter)
cases = int(input())
for case in range(cases):
	(N, K, M) = [int(i) for i in input().split()]
	n = N
	p = 0
	q = 1
	counter = 0
	m = 0
	(m, counter) = mcounter(M, counter)
	p = (pow(N, m, mod) - pow(N - 1, m, mod)) % mod
	q = pow(N, m, mod) % mod
	if counter == 1:
		n = N + K
		p = p * n + (q - p)
		q = n * q
	q = pow(q, mod - 2, mod)
	print(p % mod * (q % mod) % mod)


mod = 1000000007

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

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

def inverseMod(a, m):
	g = gcd(a, m)
	if g != 1:
		return 0
	else:
		return expo(a, m - 2, m)
t = int(input())
for i in range(t):
	n = 0
	k = 0
	m = 0
	a = 0
	b = 0
	c = 0
	d = 0
	p = 0
	q = 0
	(n, k, m) = list(map(int, input().split()))
	if m & 1:
		a = expo(n, (m + 1) // 2, mod)
		b = expo(n - 1, (m + 1) // 2, mod)
		p = a - b
		q = a
	else:
		a = expo(n, m // 2, mod)
		b = expo(n - 1, m // 2, mod)
		p = (a - b) * (n + k) % mod + b
		q = a * (n + k) % mod
	c = inverseMod(q, mod)
	d = p * c % mod
	print(d)


from math import gcd

def calc(b, po, m):
	ans = 1
	while po > 0:
		if po % 2 == 1:
			ans = ans * b % m
		po = po // 2
		b = b * b % m
	return ans

def common(n, m):
	mod = 10 ** 9 + 7
	a = calc(n, m, mod)
	b = calc(n - 1, m, mod)
	inv = calc(n, mod - 2, mod)
	inv = calc(inv, m, mod) % mod
	ans = (a - b) * inv
	ans %= mod
	return ans
t = int(input())
for z in range(t):
	(n, k, m) = [int(x) for x in input().split()]
	p = m
	mod = 10 ** 9 + 7
	if p % 2 == 0:
		m = m // 2
		num = common(n, m)
		dum = calc(n - 1, m, mod) % mod
		inv = calc(n, mod - 2, mod) % mod
		p = calc(inv, m, mod) % mod
		inv2 = calc(n + k, mod - 2, mod) % mod
		p *= inv2
		p %= mod
		dum = dum * p
		dum %= mod
		print((num + dum) % mod)
	else:
		num = common(n, p // 2 + 1)
		print(num)


modd = 1000000007

def mox(n):
	modd = 1000000007
	return pow(n, modd - 2, modd)

def get(n, tries):
	p = n - 1
	q = n
	k = p % modd * (mox(q) % modd) % modd
	return pow(k, tries, modd)
t = int(input())
for _ in range(t):
	(n, k, m) = list(map(int, input().split()))
	if m == 1:
		print(mox(n) % modd)
	else:
		flag = 0
		if m % 2 == 0:
			flag = 1
		tries = m // 2 + 1
		if flag == 0:
			ans = (1 - get(n, tries) + modd) % modd
		else:
			tries -= 1
			kk = get(n, tries) % modd
			ans = (1 - kk + modd) % modd
			ans = (ans % modd + mox(n + k) % modd * kk) % modd
		print(ans)


import math

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
t = int(input())
while t != 0:
	(n, k, m) = map(int, input().split(' '))
	mod = int(1000000007)
	if m == 1:
		nu = 1
		de = n
	elif m == 2:
		nu = n + k + (n - 1)
		de = n * (n + k)
	elif m % 2 != 0:
		x = m // 2 + 1
		n1 = pow(n, x, mod)
		n2 = pow(n - 1, x, mod)
		nu = n1 - n2
		de = n1
	elif m % 2 == 0:
		x = m // 2 + 1
		n1 = pow(n - 1, x - 1, mod)
		n2 = pow(n, x - 1, mod)
		nu = n2 - n1
		nu = nu % mod * ((n + k) % mod) % mod
		nu = (nu % mod + n1 % mod) % mod
		de = n2 % mod * ((n + k) % mod) % mod
	gcd = math.gcd(nu, de)
	nu = nu // gcd
	de = de // gcd
	ans = modinv(de, mod)
	ans = ans % mod * (nu % mod) % mod
	print(ans)
	t -= 1


from math import gcd

def modExPow(x, y):
	bigMod = 10 ** 9 + 7
	p = bigMod
	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

def modInv(a):
	bigMod = 10 ** 9 + 7
	m = bigMod
	m0 = m
	y = 0
	x = 1
	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
t = int(input())
while t:
	t -= 1
	(n, k, m) = map(int, input().split())
	bigMod = 10 ** 9 + 7
	if m % 2 == 0:
		x = int(m / 2)
		q = modExPow(n, x)
		y = modExPow(n - 1, x)
		q = q % bigMod
		q = (n + k) * q % bigMod
		p = (q - (n + k - 1) * (y % bigMod) % bigMod) % bigMod
		newq = modInv(q)
		ans = p * newq % bigMod
		print(ans)
	else:
		x = int(m / 2) + 1
		q = modExPow(n, x)
		y = modExPow(n - 1, x)
		q = q % bigMod
		p = (q - y % bigMod) % bigMod
		newq = modInv(q)
		ans = p * newq % bigMod
		print(ans)


t = int(input())
while t > 0:
	t = t - 1
	s = input()
	e = s.split(' ')
	n = int(e[0])
	k = int(e[1])
	m = int(e[2])
	j = 1000000007
	if m % 2 == 0:
		p1 = (n + k) % j
		p2 = pow(n, int(m / 2), j)
		p3 = 1 - n - k
		p4 = pow(n - 1, int(m / 2), j)
		p11 = p1 * p2 % j
		p22 = p3 * p4 % j
		p = (p11 + p22) % j
		q = p11
		qin = pow(q, j - 2, j) % j
		print(p * qin % j)
	else:
		p1 = pow(n, int(m / 2) + 1, j)
		p2 = pow(n - 1, int(m / 2) + 1, j)
		p = (p1 - p2) % j
		q = p1
		qin = pow(q, j - 2, j) % j
		print(p * qin % j)


z = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k, m) = map(int, input().split())
	t = m // 2 if m / 2 - m // 2 == 0 else m // 2 + 1
	den = pow(n, t, z)
	x = pow(n - 1, t, z)
	num = den - x
	if m % 2 == 1:
		print(pow(den, z - 2, z) * num % z)
	else:
		num = den * (n + k) - x * (n + k - 1)
		den = den * (n + k)
		print(pow(den, z - 2, z) * num % z)


c = 10 ** 9 + 7

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)
for _ in range(int(input())):
	(n, k, m) = [int(k) for k in input().split()]
	if m % 2 == 1:
		p = (pow(n, (m + 1) // 2, c) - pow(n - 1, (m + 1) // 2, c)) % c
		q = pow(n, (m + 1) // 2, c)
	else:
		p = ((n + k) % c * pow(n, m // 2, c) % c - (n + k - 1) % c * pow(n - 1, m // 2, c) % c) % c
		q = pow(n, m // 2, c) * (n + k) % c % c
	print(p % 1000000007 * (modInverse(q, 1000000007) % 1000000007) % 1000000007)


import math as ma
import sys
from sys import exit
from decimal import Decimal as dec
from itertools import permutations
M = 1000000007

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

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

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

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = nu()
for i in range(t):
	(n, k, m) = num()
	lol = m // 2
	x = 1
	x += lol
	if m % 2 == 0:
		x = (m - 1) // 2 + 1
	P = (pow(n, x, M) - pow(n - 1, x, M) + M) % M
	Q = pow(n, x, M)
	G = find_gcd(P, Q)
	P //= G
	Q //= G
	P = P * pow(Q, M - 2, M) % M
	if m % 2 == 0:
		A = pow(n - 1, x, M)
		B = pow(n, x, M) * (n + k) % M
		G = find_gcd(A, B)
		A //= G
		B //= G
		P = (P + A * pow(B, M - 2, M) % M) % M
	print(P)


from fractions import Fraction

def modpow(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

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
for _ in range(int(input())):
	(n, k, m) = [int(x) for x in input().split(' ')]
	num = 0
	den = 0
	if n == 1:
		print(1)
	else:
		if n > k:
			n = n % k
			if n == 0:
				n = k
			m -= 1
		p = int(m / 2 + 1) - 1
		den = modpow(n, p, 1000000007)
		num = modpow(n, p, 1000000007) - modpow(n - 1, p, 1000000007)
		den1 = modpow(n, p, 1000000007)
		num1 = modpow(n - 1, p, 1000000007)
		if m % 2 == 0:
			n = n + k
		num1 = num1 * 1
		den1 = den1 * n
		top = num * den1 + num1 * den
		bot = den * den1
		answer = top * modinv(bot, 1000000007) % 1000000007
		print(answer)


raw_input = input
mod = 10 ** 9 + 7
for _ in range(int(raw_input())):
	(n, k, m) = map(int, raw_input().split())
	if m % 2 == 1:
		a = pow(n, m // 2 + 1, mod)
		b = pow(n - 1, m // 2 + 1, mod)
		num = a - b
		den = a
		print(num % mod * (pow(den, mod - 2, mod) % mod) % mod)
	else:
		a = pow(n, m // 2, mod)
		b = pow(n - 1, m // 2, mod)
		num = (n + k) * (a - b) + b
		den = (n + k) * a
		print(num % mod * (pow(den, mod - 2, mod) % mod) % mod)


import sys

def inverse(fir, nm):
	return por(fir, nm - 2, nm)

def por(x, y, nm):
	if y == 0:
		return 1
	p1 = por(x, y // 2, nm) % nm
	p1 = p1 * p1 % nm
	if y % 2 == 0:
		return p1
	else:
		return x * p1 % nm

def gcd(fir, b):
	if fir == 0:
		return b
	return gcd(b % fir, fir)
for _ in range(int(input())):
	(n, k, nm) = tuple(list(map(int, input().split())))
	if n == 1:
		print(1)
		continue
	elif nm == 1:
		p1 = 1
		p2 = n
		print(inverse(p2, 1000000007))
	elif nm % 2 != 0:
		p1 = por(n, nm // 2 + 1, 1000000007) - por(n - 1, nm // 2 + 1, 1000000007)
		p2 = por(n, nm // 2 + 1, 1000000007)
		g = gcd(p1, p2)
		if g == 1:
			print(p1 % 1000000007 * (inverse(p2, 1000000007) % 1000000007) % 1000000007)
		else:
			print(p1 // g % 1000000007 * (inverse(p2 // g, 1000000007) % 1000000007) % 1000000007)
	else:
		nm -= 1
		pp = por(n, nm // 2 + 1, 1000000007) - por(n - 1, nm // 2 + 1, 1000000007)
		qq = por(n, nm // 2 + 1, 1000000007)
		nm += 1
		ppp = por(n - 1, nm // 2, 1000000007)
		qqq = por(n, nm // 2, 1000000007) * (n + k) % 1000000007
		p1 = (pp * qqq % 1000000007 + ppp * qq % 1000000007) % 1000000007
		p2 = qqq * qq % 1000000007
		g = gcd(p1, p2)
		if g == 1:
			print(p1 % 1000000007 * (inverse(p2, 1000000007) % 1000000007) % 1000000007)
		else:
			print(p1 // g % 1000000007 * (inverse(p2 // g, 1000000007) % 1000000007) % 1000000007)


import math
mod = 1000000007

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)

def gcd(a, b):
	return math.gcd(a, b)

def power1(x, y):
	if y == 0:
		return 1
	temp = power1(x, int(y / 2))
	if y % 2 == 0:
		return temp * temp
	elif y > 0:
		return x * temp * temp
	else:
		return temp * temp / x
T = int(input())
while T:
	a = [int(j) for j in input().split()]
	N = a[0]
	K = a[1]
	M = a[2]
	if N == 1:
		result = 1
	else:
		if M % 2:
			nu = power(N, int((M + 1) / 2), mod) - power(N - 1, int((M + 1) / 2), mod)
			deno = power(N, int((M + 1) / 2), mod)
		else:
			nu = power(N, int(M / 2), mod) * (N + K) - power(N - 1, int(M / 2), mod) * (N + K - 1)
			deno = power(N, int(M / 2), mod) * (N + K)
		gcd = math.gcd(nu, deno)
		nu = nu // gcd
		deno = deno // gcd
		deno = modInverse(deno, mod)
		result = nu % mod * (deno % mod) % mod
	print(result)
	T -= 1