Game on Sum (Easy Version)
Contest: Codeforces Round 767 (Div. 1)
Difficulty rating: 2100
Tags: combinatorics, dp, games, math

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 format:
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 format:
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} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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}$$$.

Example input:
7
3 3 2
2 1 10
6 3 10
6 4 10
100 1 1
4 4 0
69 4 20

Example output:
6
5
375000012
500000026
958557139
0
49735962

Editorial:
What is the answer for $$$n = 2$$$, $$$m = 1$$$?
Let's call the number Alice picks on the first turn $$$x$$$.
If $$$x$$$ is small, Bob can add it, and then Alice will have to pick $$$0$$$ on the last turn since Bob will definitely subtract it from the score if it isn't $$$0$$$, meaning the score ends up being $$$x$$$.
If Alice picks a big number, Bob can subtract it. Then Alice will pick the biggest number she can on the last turn, ending up with a score of $$$k-x$$$.
Since Bob tries to minimize the score of the game, Alice should pick an $$$x$$$ such that it maximizes the value of $$$min(x, k-x)$$$. $$$x$$$ and $$$k-x$$$ are both linear (straight line) functions on $$$x$$$. The $$$x$$$ value that maximizes the minimum of two lines is their intersection. The intersection of the lines $$$x$$$ and $$$k-x$$$ is at $$$x = k/2$$$. So Alice should pick $$$x = k/2$$$ in the optimal game where $$$n = 2$$$, $$$m = 1$$$.
To generalize the solution to arbitrary $$$n$$$ and $$$m$$$, we can use DP. Let $$$DP[i][j]$$$ what the score would be if $$$n = i$$$, $$$m = j$$$.
Our base cases will be
• $$$DP[i][0] = 0$$$ since if Bob doesn't have to add anything, Alice has to always pick $$$0$$$.
• $$$DP[i][i] = i \cdot k$$$ since if Bob always has to add, Alice can just pick $$$k$$$ every time.
When Bob adds to the score, the rest of the game will be the same as a game with $$$1$$$ fewer turns and $$$1$$$ fewer forced adds, except the game score is offset by Alice's number. When Bob subtracts from the score, the rest of the game will be the same as a game with $$$1$$$ fewer turns except the game score is offset by negative Alice's number.
Bob will take the minimum of these, so the $$$DP$$$ transition will be
$$$DP[i][j] = min(DP[i-1][j-1]+x, DP[i-1][j]-x)$$$ for $$$x$$$ that maximizes this value.
This is the same problem as the $$$n=2$$$ case resulting in the intersection between lines. The score at this intersection simplifies nicely to $$$DP[i][j] = (DP[i-1][j-1]+DP[i-1][j])/2$$$
This $$$O(n\cdot m)$$$ solution is fast enough to pass the easy version of this problem.