IIOT 2023 : International Final - Chiếc mũ kì diệu

Tác giả:

Dạng bài

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Tại trường phù thủy Berlandian, Wartshog, mỗi năm, học sinh mới sẽ được phân chia vào \(3\) dãy nhà: Andorgryff, Bufflehuff, và Clawenrave. Sự phân chia này sẽ được thực hiện bởi \(1\) chiếc mũ. Quá trình rất đơn giản, từng học sinh sẽ đội chiếc mũ (theo một thứ tự nhất định), và chiếc mũ sẽ hét lên dãy nhà mà học sinh ấy sẽ phải ở.

Năm nay, có \(A, B\) và \(C\) khu trong \(3\) dãy nhà riêng biệt đó, và có tổng cộng \(A + B + C\) học sinh, cho nên, sẽ có \(A\) học sinh ở Andorgryff, \(B\) học sinh ở Bufflehuff, và \(C\) học sinh ở Clawenrave. Chiếc mũ có thêm một điều nữa, đó là: không có \(2\) học sinh liên tiếp nào được cho vào chung 1 dãy nhà được.
Vì đang bận train cho cuộc thi phù thủy sắp tới nên Bác bảo vệ không thể quản được, nên bác ấy đã nhờ bạn một việc, đó là bạn hãy tính số cách tồn tại để phân chia học sinh vào các dãy nhà. Vì kết quả có thể rất lớn nên bạn chỉ cần đưa ra đáp án sau khi chia lấy dư cho \(10^9 + 7\). Hai cách phân chia được gọi là khác nhau khi có ít nhất 1 học sinh được cho vào một dãy nhà khác.

Input, Output and Scoring

Input

Dòng đầu tiên nhập \(T\) là số testcase, Sau đó với \(T\) dòng, nhập ba số \(A, B, C\).

Output

Với mỗi testcase, bạn phải in ra một số là số cách phân chia học sinh sau khi được chia lấy dư cho \(10^9 + 7\).

Contraints

\(1 \le T \le 20\)
\(0 \le A, B, C \le 100000\)
\(A + B + C \geq 1\)

Scoring

Bài của bạn sẽ được chấm theo thể thức IOI, tức là để có điểm của một subtask nào đó, bạn cần phải đúng hết tất cả testcase trong subtask ấy.
- Subtask \(1\) \((0pts)\): Test ví dụ.
- 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)\): Không có giới hạn gì thếm.

Example

Input

5
2 3 0
2 2 1
4 1 1
100 100 100
100000 100000 1

Output

Note

Đối với testcase đầu tiên, chúng ta chỉ có 1 cách chia hợp lý : BABAB .
Đối với testcase số hai, Có \(12\) cách chia hợp lý là : ABABC, ABACB, ABCAB, ABCBA, ACBAB, BABAC, BABCA, BACAB, BACBA, BCABA, CABAB, CBABA.
Đối với testcase số ba, bạn chia kiểu gì đi chăng nữa thì sẽ có ít nhất 2 học sinh liên tiếp trong cùng 1 dãy nhà A. .

Source: IIOT International Final 2023 - Hosted in Port Said - Egypt

Bình luận

Không có bình luận nào.