407760: GYM102890 K K contestants

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. K contestantstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Elisa's high school is preparing to compete on the 2020 regional algorithms competition. The high school should register exactly $$$K$$$ contestants to the competition, as they believe the students on the last grade are the most capable to win the competition, they will register the $$$K$$$ contestants only from the last grade. The high school has $$$3$$$ groups in the last grade, the $$$A$$$, $$$B$$$, and $$$C$$$. Teachers from the $$$C$$$ group say students in this group have better grades in mathematics than those in groups $$$A$$$ and $$$B$$$, and, therefore, they say there should be exactly $$$c$$$ students from group $$$C$$$ in the $$$K$$$ registered contestants. To make sure all the groups have representation in the competition, the school principal decided that at least one student from each group should be registered.

Given the number of students in groups $$$A$$$, $$$B$$$, and $$$C$$$, the number of contestants $$$K$$$ that should be registered by the school in the competition, and the number of $$$c$$$ students from group $$$C$$$ that should be registered in the competition. Find the number of different ways the school can choose the $$$K$$$ students to register in the competition.

Input

The first line of input contains a single integer $$$T$$$, the number of test cases. Each of the next $$$T$$$ ($$$1 \leq T \leq 10^5$$$) lines, describe a test case, containing a single line with $$$5$$$ integer numbers separated by a space, representing, respectively, the number of students in group $$$A$$$, the number of students in group $$$B$$$, the number of students in group $$$C$$$, the number of students $$$K$$$ to be registered in the competition, and the number of students $$$c$$$ from group $$$C$$$ that should be registered in the competition. It is guaranteed that: $$$1 \leq A, B, C, K \leq 10^5$$$ , $$$1 \leq c \leq C$$$

Output

For each test case in the input, print a single line with an integer representing the number of different ways the school can choose the $$$K$$$ students to register in the competition. As this number can be big, print it modulo $$$1000000007$$$

ExampleInput
2
3 3 3 7 2
3 3 3 10 2
Output
18
0

加入题单

上一题 下一题 算法标签: