IIOT 2023 : International Final - Chiếc mũ kì diệu
Xem PDFIn the Berlandian school of witchcraft and wizardry, Wartshog, each year newcomer students are distributed between three houses: Andorgryff, Bufflehuff, and Clawenrave. The distribution is done by a hat, called the Distributing Hat. The students put on the hat one by one (in a certain fixed order), and the hat shouts out loud the name of the house to which the student will belong.
This year, there are \(A, B,\) and \(C\) places in the three houses respectively, and the number of new students is \(A + B + C\), so there will be exactly \(A\) new students in Andorgryff, \(B\) in Bufflehuff, and \(C\) in Clawenrave. The Distributing Hat follows one additional rule: no two consecutive students will be put in the same house.
Can you tell how many different ways exist for distributing the students between the houses? Since this number might be very big, you need to give the answer modulo \(10^9 + 7\). Two distributions are considered different if at least one student is assigned to a different house.
Input, Output and Scoring
Input
- The first line contains \(T\), the number of test cases. Each of the following \(T\) lines contains three integer numbers \(A, B\) and \(C\).
Output
- For each test case, output a single number on a separate line, the number of different ways to distribute the students, modulo \(10^9 + 7\).
Contraints
- \(1 \le T \le 20\)
- \(0 \le A, B, C \le 100000\)
- \(A + B + C \geq 1\)
Scoring
- Your program will be tested against several test cases grouped in subtasks. In order to obtain the score of a subtask, your program needs to correctly solve all of its test cases.
- Subtask \(1\) \((0pts)\): Example.
- Subtask \(2\) \((6pts)\): \(C = 0\).
- Subtask \(3\) \((9pts)\): \(A + B + C \le 10\).
- Subtask \(4\) \((19pts)\): \(A, B, C \le 100\).
- Subtask \(5\) \((23pts)\): \(A, B, C \le 2000\).
- Subtask \(6\) \((14pts)\): \(C \le 2\).
- Subtask \(7\) \((29pts)\): No additional limitations.
Example
Input
5
2 3 0
2 2 1
4 1 1
100 100 100
100000 100000 1
Output
1
12
0
105481704
600000
Note
- In the first sample case, there is only one possible distribution:
BABAB(here we write the initial letter of the chosen house for each student in order). - In the second sample case, the \(12\) possible ways are:
ABABC,ABACB,ABCAB,ABCBA,ACBAB,BABAC,BABCA,BACAB,BACBA,BCABA,CABAB,CBABA. - In the third sample case, there will be at least two consecutive \(A-s\) in any distribution, so the hat has no way to distribute the students.
Source: IIOT International Final 2023 - Hosted in Port Said - Egypt
Bình luận