This is the easy version of the problem. The difference is the constraints on $n$, $m$ and $t$. You can make hacks only if all versions of the problem are solved.

Alice and Bob are given the numbers $n$, $m$ and $k$, and play a game as follows:

The game has a score that Alice tries to maximize, and Bob tries to minimize. The score is initially $0$. The game consists of $n$ turns. Each turn, Alice picks a real number from $0$ to $k$ (inclusive) which Bob either adds to or subtracts from the score of the game. But throughout the game, Bob has to choose to add at least $m$ out of the $n$ turns.

Bob gets to know which number Alice picked before deciding whether to add or subtract the number from the score, and Alice gets to know whether Bob added or subtracted the number for the previous turn before picking the number for the current turn (except on the first turn since there was no previous turn).

If Alice and Bob play optimally, what will the final score of the game be?


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.

Each test case consists of a single line containing the three integers, $n$, $m$, and $k$ ($1 \le m \le n \le 2000, 0 \le k < 10^9 + 7$) — the number of turns, how many of those turns Bob has to add, and the biggest number Alice can choose, respectively.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.


-----Output-----

For each test case output a single integer number — the score of the optimal game modulo $10^9 + 7$.

Formally, let $M = 10^9 + 7$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} mod M$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.


-----Examples-----

Input
7
3 3 2
2 1 10
6 3 10
6 4 10
100 1 1
4 4 0
69 4 20
Output
6
5
375000012
500000026
958557139
0
49735962


-----Note-----

In the first test case, the entire game has $3$ turns, and since $m = 3$, Bob has to add in each of them. Therefore Alice should pick the biggest number she can, which is $k = 2$, every turn.

In the third test case, Alice has a strategy to guarantee a score of $\frac{75}{8} \equiv 375000012 \pmod{10^9 + 7}$.

In the fourth test case, Alice has a strategy to guarantee a score of $\frac{45}{2} \equiv 500000026 \pmod{10^9 + 7}$.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Combinatorics

Game theory

Mathematics


Solutions:
import sys
input = sys.stdin.readline
get_int = lambda : int(input().rstrip())
get_arr = lambda : [int(w) for w in input().split()]
get_str = lambda : input().rstrip()
mod = 10 ** 9 + 7
t = get_int()
mx = 10 ** 4 + 1
fac = [1]
rfac = [1]
for i in range(1, mx):
	fac.append(fac[-1] * i)
	rfac.append(rfac[-1] * pow(i, -1, mod))
	fac[-1] %= mod
	rfac[-1] %= mod

def cnk(n, k):
	return fac[n] * rfac[n - k] * rfac[k] % mod

def find(n, m, k):
	arr = [0] * (n - m)
	for i in range(m + 1):
		arr.append(2 * i)
	res = 0
	for i in range(len(arr)):
		res += cnk(n, i) * arr[i]
		res %= mod
	return res * k * pow(2, -n, mod) % mod
for _ in range(t):
	(n, m, k) = get_arr()
	print(find(n, m, k))


import sys

def solve():
	inp = sys.stdin.readline
	(n, m, k) = map(int, inp().split())
	MOD = 1000000007
	i2 = pow(2, MOD - 2, MOD)
	dp = [[-1e+30] * (i + 1) for i in range(n + 1)]
	dp[1][0] = 0
	dp[1][1] = k
	for i in range(2, n + 1):
		dp[i][0] = dp[i - 1][0]
		for j in range(1, i):
			dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) * i2 % MOD
		dp[i][i] = (dp[i - 1][i - 1] + k) % MOD
	print(dp[n][m])

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
import math
R = lambda : sys.stdin.readline().rstrip()
MIS = lambda : map(int, R().split())
sys.setrecursionlimit(10 ** 6)
mod = 1000000007

def f(a, b):
	if dp[a][b] != -1:
		return dp[a][b]
	if a == b:
		dp[a][b] = K * a % mod
		return dp[a][b]
	if b == 0:
		dp[a][b] = 0
		return dp[a][b]
	dp[a][b] = (f(a - 1, b) + f(a - 1, b - 1)) % mod
	if dp[a][b] & 1:
		dp[a][b] *= mod // 2 + 1
	else:
		dp[a][b] //= 2
	return dp[a][b]
for _ in range(int(R())):
	(N, M, K) = MIS()
	dp = [[-1] * (M + 1) for _ in range(N + 1)]
	print(f(N, M) % mod)


MOD = 10 ** 9 + 7
solve_solution = [[-1 for _ in range(2001)] for _ in range(2001)]

def solve(a, b):
	if solve_solution[a][b] != -1:
		return solve_solution[a][b]
	for i in range(a + 1):
		for j in range(b + 1):
			if solve_solution[i][j] == -1:
				if i == 0:
					solve_solution[i][j] = 0
					continue
				if j == 0:
					solve_solution[i][j] = i
					continue
				res = solve_solution[i][j - 1] - solve_solution[i - 1][j]
				if res < 0:
					res += MOD
				res *= (MOD + 1) // 2
				res += solve_solution[i - 1][j]
				res %= MOD
				solve_solution[i][j] = res
	return solve_solution[a][b]
T = int(input())
for _ in range(T):
	(n, m, k) = map(int, input().split())
	a = m
	b = n - m
	res = solve(a, b)
	res = res * k % MOD
	print(res)


M = int(1000000000.0 + 7)
inv2_modM = int(500000000.0 + 4)
t = int(input())
for test in range(t):
	(n, m, k) = map(lambda x: int(x), input().split())
	dp = [[0] * (m + 1) for _ in range(n + 1)]
	for i in range(min(n + 1, m + 1)):
		dp[i][i] = i * k % M
	for i in range(1, n + 1):
		for j in range(1, min(i, m + 1)):
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) * inv2_modM % M
	print(dp[n][m])


t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	mod = int(1000000000.0 + 7)
	dp = [[0] * (n + 1) for i in range(n + 1)]
	for i in range(n + 1):
		dp[i][i] = i * k % mod
	for i in range(1, n + 1):
		for j in range(1, i):
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) * (mod + 1) // 2 % mod
	print(dp[n][m])