Codeforces Round 921 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

math

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Balanced Subsequences

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters '+' and '1'. For example, sequences '(())()', '()', and '(()(()))' are balanced, while ')(', '(()', and '(()))(' are not.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

You are given three integers $$$n$$$, $$$m$$$ and $$$k$$$. Find the number of sequences consisting of $$$n$$$ '(' and $$$m$$$ ')', such that the longest balanced subsequence is of length $$$2 \cdot k$$$. Since the answer can be large calculate it modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3 \cdot 10^3$$$). Description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m, k \le 2 \cdot 10^3$$$)

Output

For each test case, print one integer — the answer to the problem.

Example

Input

32 2 23 2 33 2 1

Output

2 0 4

Note

For the first test case "()()", "(())" are the $$$2$$$ sequences

For the second test case no sequence is possible.

For the third test case ")((()", ")(()(", ")()((", "())((" are the $$$4$$$ sequences.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/11/2024 21:26:16 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|