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

Every time Rami comes up with an idea for a nice problem, his grandfather Saeed rejects it, claiming that it takes a lot of work to write tests for such a problem. Therefore, Rami spent days thinking about a problem with only three numbers as the input. Finally, he thought up such a problem and ran happily to his grandfather, shouting:

You are given three integers $N$, $M$ and $K$. Find the number of sequences $A_{1}, A_{2}, \ldots, A_{N}$ such that:
For each valid $i$, $A_{i}$ is an integer in the range $[0, M-1]$.
Let's define $N$ prefix sums of $A$ as $S_{i} = \sum_{j=1}^i A_{j}$, where $1 ≤ i ≤ N$. At least $K$ of these prefix sums are divisible by $M$.

Let's see if you can solve this simple problem! Rami knows that the answer could be really large, so you should compute it 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$, $M$ and $K$.

------  Output ------
For each test case, print a single line containing one integer — the number of valid sequences modulo $10^{9}+7$.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ K ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{9}$
the sum of $N$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
2

3 2 2

3 2 1
----- Sample Output 1 ------ 
4

7
----- explanation 1 ------ 
For $N = 3$ and $M = 2$, there are eight possible sequences satisfying the first condition: $[0,0,0]$, $[0,0,1]$, $[0,1,0]$, $[0,1,1]$, $[1,0,0]$, $[1,0,1]$, $[1,1,0]$ and $[1,1,1]$. Their prefix sums are $[0,0,0]$, $[0,0,1]$, $[0,1,1]$, $[0,1,2]$, $[1,1,1]$, $[1,1,2]$, $[1,2,2]$ and $[1,2,3]$ respectively.

As we can see, there are:
- one sequence with $0$ prefix sums divisible by $2$: $[1,0,0]$
- three sequences with exactly $1$ prefix sum divisible by $2$: $[0,1,0]$, $[1,0,1]$, $[1,1,1]$
- three sequences with $2$ prefix sums divisible by $2$: $[0,0,1]$, $[0,1,1]$, $[1,1,0]$
- one sequence with $3$ prefix sums divisible by $2$: $[0,0,0]$

Difficulty: HARD
Tags: Number theory

Combinatorics

Mathematics

Range queries
Skill types: Range queries

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def mm(a, b, c):
	if b == 0:
		return 1
	ans = 1
	if b % 2 == 1:
		ans *= a
	ans = mm(a, b // 2, c) ** 2 * ans % c
	return ans

def mm2(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 c(a, b):
	aa = pre[a]
	aa *= pp[b]
	aa *= pp[a - b]
	return aa % mod
t = int(input())
mod = 10 ** 9 + 7
pre = [1]
for i in range(1, 10 ** 5 + 1):
	pre.append(pre[-1] * i % mod)
pp = []
for i in pre:
	pp.append(mm(i, mod - 2, mod))
for _ in range(t):
	(n, m, k) = map(int, input().split())
	tot = 0
	p = [1]
	for i in range(n - k + 1):
		p.append(p[-1] * (m - 1) % mod)
	for i in range(k, n + 1):
		prev = tot
		tot += c(n, i) * p[n - i]
		tot %= mod
	print(tot)


mod = 10 ** 9 + 7

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
f = [1 for i in range(10 ** 5 + 5)]
finv = [1 for i in range(10 ** 5 + 5)]
for i in range(1, 10 ** 5 + 5):
	f[i] = i * f[i - 1]
	f[i] %= mod
for i in range(10 ** 5 + 5):
	finv[i] = power(f[i], mod - 2, mod)
	finv[i] %= mod
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	ans = 0
	for i in range(k, n + 1):
		ncr = f[n] * finv[i] * finv[n - i]
		ncr %= mod
		expo = power(m - 1, n - i, mod)
		ans += ncr * expo
		ans %= mod
	print(ans % mod)


import sys
MAXN = pow(10, 5) + 10
mod = pow(10, 9) + 7
fact = [0] * MAXN
inv = [0] * MAXN

def precompute():
	fact[0] = 1
	inv[0] = 1
	for i in range(1, MAXN):
		fact[i] = fact[i - 1] * i
		fact[i] %= mod
		inv[i] = pow(fact[i], mod - 2, mod)
precompute()

def ncr(x, y):
	res = fact[x] * inv[y]
	res %= mod
	res *= inv[x - y]
	res %= mod
	return res
t = int(sys.stdin.readline())
for _ in range(t):
	(n, m, k) = map(int, sys.stdin.readline().split())
	res = 0
	for i in range(k, n + 1):
		res += ncr(n, i) * pow(m - 1, n - i, mod)
		res %= mod
	print(res)


mod = int(1000000007)
fact = [0] * 100005
invfact = [0] * 100005

def powe(a, b):
	if b == 0:
		return 1
	temp = powe(a, int(b / 2))
	temp = temp * temp % mod
	if b % 2 == 1:
		temp = temp * a % mod
	return temp

def pre():
	fact[0] = 1
	invfact[0] = 1
	for x in range(1, 100005):
		fact[x] = fact[x - 1] * x % mod
		invfact[x] = powe(fact[x], int(mod - 2))

def comb(n, r):
	if r > n:
		return 0
	if n == r or r == 0:
		return 1
	A = fact[n]
	B = invfact[r]
	A = A * B % mod
	C = invfact[n - r]
	A = A * C % mod
	return A
t = int(input())
pre()
for tt in range(t):
	arr = input()
	arr = list(map(int, arr.split(' ')))
	n = arr[0]
	m = arr[1]
	k = arr[2]
	ans = powe(m, n)
	for i in range(0, k):
		b = comb(n, i)
		c = powe(m - 1, n - i)
		b = b * c % mod
		ans -= b
		ans %= mod
		ans = (ans + mod) % mod
	print(ans)


M = 10 ** 9 + 7

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
a = [1]
for i in range(1, 10 ** 5 + 2):
	a.append(a[-1] * i % M)
for i in range(int(input())):
	(n, m, k) = map(int, input().split())
	ans = 0
	for j in range(k, n + 1):
		ans += pow(m - 1, n - j, M) * modInverse(a[j] * a[n - j], M) * a[n]
		ans %= M
	print(ans)


mod = 1000000007
MOD = 998244353
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
it = lambda : tuple(map(int, input().split()))
ls = lambda : list(input())

class Triplet:

	def __init__(self, x, y, gd):
		self.x = x
		self.y = y
		self.gd = gd

def extendedGCD(a, b):
	if b == 0:
		return Triplet(1, 0, a)
	ans = extendedGCD(b, a % b)
	return Triplet(ans.y, ans.x - a // b * ans.y, ans.gd)

def modInverse(a, m):
	z = extendedGCD(a, m).x
	return z
for _ in range(ii()):
	(n, m, k) = f()
	srik = [0] * k
	ummi = [0] * (n + 1)
	srik[0] = 1
	for i in range(1, k):
		srik[i] = srik[i - 1] * (n - i + 1) % mod
		srik[i] = srik[i] * modInverse(i, mod) % mod
	ummi[0] = 1
	ans = 1
	for i in range(1, n + 1):
		ummi[i] = ummi[i - 1] * (m - 1) % mod
		ans = ans * m % mod
	for i in range(k):
		ans = (mod + ans - srik[i] * ummi[n - i] % mod) % mod
	print(ans)


M = 10 ** 9 + 7
N = 10 ** 5 + 1
f = [1] * N
for i in range(1, N):
	f[i] = i * f[i - 1] % M
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	s = sum((pow(f[i] * f[n - i], M - 2, M) * pow(m - 1, n - i, M) for i in range(k, n + 1)))
	print(f[n] * s % M)


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 modDivide(a, b, m):
	a = a % m
	inv = modinv(b, m)
	if inv == -1:
		return None
	else:
		return inv * a % m

def power(x, y, MOD):
	if y == 0:
		return 1
	a = power(x, y // 2, MOD)
	if y % 2 == 0:
		return a * a % MOD
	else:
		return a * a * x % MOD
MOD = 10 ** 9 + 7
t = int(input())
fact = [1]
for i in range(1, 10 ** 5 + 10):
	fact.append(fact[-1] * i % MOD)
for t_ in range(t):
	(n, m, k) = map(int, input().split())
	ans = 0
	for i in range(n - k + 1):
		ans += pow(m - 1, i, MOD) * modDivide(fact[n], fact[i] * fact[n - i] % MOD, MOD) % MOD
		ans %= MOD
	print(ans)