-----Problem Statement-----
Sereja has a sequence of n integers a[1], a[2], ..., a[n]. Sereja can do following transformation of the array:

- create a new sequence of n integers b[1], b[2], ..., b[n]in this way:    (1 ≤ i ≤ n)

- Replace the sequence a by b, i.e., a[i] = b[i] for all i in [1, n] 

Sereja decided to use his transformation k times. Then he computed the value of      , where r — the sequence obtained after k transformations of sequence a, as described above.

Sereja lost sequence a, but he was left with the numbers q(r) and k. Now Sereja is interested in the question : what is the number of the sequences of the integers с[1], с[2], ..., с[n], such that 1 ≤ c[i] ≤ m and q(d) = q(r), where d — the sequence obtained after k transformations of sequence c, as described above.

-----Input-----
The first lines contains a single integer T, denoting the number of test cases. Each  test case consist of four integers : n, m, q(r), k.

-----Output-----
In a single line print the remainder of division the answer of the problem on number 10^9 + 7.

-----Constraints-----

- 1 ≤ T ≤ 10000
- 1 ≤ n, m, q(r), k ≤ 10^9

-----Example-----
Input:
3
1 1 1 1
2 2 1 1
2 3 1 1

Output:
0
2
4

Difficulty: MEDIUM_HARD
Tags: Number theory

Combinatorics

Mathematics

Starter code:

Solutions:
T = int(input())
Ans = ''
for t in range(T):
	(n, m, Qr, k) = map(int, input().split())
	if Qr + 1 > m:
		Ans += '0\n'
		continue
	f = m - Qr
	x = pow(Qr + 1, n, 10 ** 9 + 7)
	x -= 2 * pow(Qr, n, 10 ** 9 + 7)
	x += pow(Qr - 1, n, 10 ** 9 + 7)
	x *= f
	x %= 10 ** 9 + 7
	Ans += str(x) + '\n'
print(Ans, end='')


T = int(input())
while T > 0:
	T -= 1
	(n, m, q, k) = map(int, input().split())
	if n == 1 or q > m:
		print(0)
		continue
	mod = 10 ** 9 + 7
	ans = (m - q) % mod
	ans = ans * (pow(q + 1, n, mod) + pow(q - 1, n, mod) - 2 * pow(q, n, mod)) % mod
	print(ans % mod)


def mod(a, b, c):
	x = 1
	y = a
	while b > 0:
		if b % 2 == 1:
			x = x * y % c
		y = y * y % c
		b /= 2
	return x % c
t = int(input())
num = 10 ** 9 + 7
for i in range(t):
	(n, m, q, k) = list(map(int, input().split()))
	if m <= q:
		print(0)
	else:
		a1 = m - q
		a2 = mod(q + 1, n, num)
		a3 = mod(q - 1, n, num)
		a4 = mod(q, n, num)
		a5 = a2 - 2 * a4 + a3
		ans = a1 * a5
		print(ans % num)


import sys
inp = sys.stdin
M = int(1000000007)

def expopowM(x, n):
	result = int(1)
	a = int(x) % M
	b = int(n)
	while b != 0:
		if b % 2 == 1:
			result = int(result * a) % M
		b = int(b / 2)
		a = int(a * a) % M
	return result
t = int(input())
while t > 0:
	(n, m, q, k) = map(int, inp.readline().split())
	if n == 1:
		print(0)
	else:
		if m - q <= 0:
			z = 0
		else:
			x = expopowM(q, n)
			z = expopowM(q + 1, n)
			y = expopowM(q - 1, n)
			z = (z - x - (x - y)) % M
			if z < 0:
				z = z + M
			z = z * (m - q) % M
		print(z)
	t -= 1


class Main:

	def __init__(self):
		iterable = self.__standard()
		self.__solution(iterable)

	def __solution(self, iterable):
		prime = 10 ** 9 + 7
		(cases,) = map(int, next(iterable).split())
		for _test in range(cases):
			(size, limit, delta, _count) = map(int, next(iterable).split())
			slots = limit - delta
			if slots < 1:
				print(0)
				continue
			result = pow(delta + 1, size, prime) - 2 * pow(delta, size, prime) + pow(delta - 1, size, prime)
			result *= slots
			print(result % prime)

	def __test(self):
		yield '3'
		yield '1 1 1 1'
		yield '2 2 1 1'
		yield '2 3 1 1'

	def __standard(self):
		try:
			while True:
				yield input()
		except EOFError:
			pass
Main()


MOD = 1000000007

def one_test(n, m, q, k):
	if q >= m:
		return 0
	if q == 0:
		return m
	return (m - q) * (pow(q + 1, n, MOD) - 2 * pow(q, n, MOD) + pow(q - 1, n, MOD)) % MOD
t = int(input())
for i in range(t):
	(n, m, q, k) = map(int, input().split())
	print(one_test(n, m, q, k))


mod = 10 ** 9 + 7

def f(n, m, d):
	if n == 1 or m <= d:
		return 0
	r = (pow(d + 1, n, mod) - pow(d, n, mod) * 2 + pow(d - 1, n, mod)) % mod
	r = r * (m - d) % mod
	return r
R = lambda : map(int, input().split())
T = int(input())
while T > 0:
	T -= 1
	(n, m, d, k) = R()
	print(f(n, m, d))


MODULO = 10 ** 9 + 7

def powfast(X, Y):
	if Y == 0:
		return 1
	if Y % 2:
		return powfast(X, Y - 1) * X % MODULO
	V = powfast(X, Y // 2)
	return V * V % MODULO
T = int(input())
for _ in range(T):
	(N, M, K, _) = [int(x) for x in input().split()]
	if N == 1:
		print(0)
		continue
	if M <= K:
		print(0)
		continue
	answer = powfast(K + 1, N) - 2 * powfast(K, N) + powfast(K - 1, N)
	while answer < 0:
		answer += MODULO
	answer = answer * (M - K) % MODULO
	print(answer)


def pow_mod(base, exp, N):
	result = 1
	while exp > 0:
		if exp % 2 == 1:
			result = result * base % N
		exp = exp >> 1
		base = base * base % N
	return result
N = 1000000007
t = int(input())
for i in range(t):
	[n, m, d, k] = input().split(' ')
	n = int(n)
	m = int(m)
	d = int(d)
	k = int(k)
	if m > d:
		t1 = m - d
		t2 = pow_mod(d + 1, n, N)
		t3 = pow_mod(d, n, N)
		t4 = pow_mod(d - 1, n, N)
		ans = (t2 - 2 * t3 + t4) * t1 % N
		print(ans)
	else:
		print('0')