Bedao OI Contest 5 - Sắp xếp chữ cái

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: ordletter.inp
Output: ordletter.out

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Vì đạt được thành tích cao trong kỳ thi HSGQG vừa qua, bố mẹ Via quyết định tặng cậu ~n~ bộ đồ chơi xếp hình được đánh số từ ~1~ đến ~n~. Bộ đồ chơi thứ ~i~ bao gồm ~a_i~ ký tự ~A~ và ~b_i~ ký tự ~B~. Via đưa ra một trò chơi như sau:

Đầu tiên Via sẽ chọn ra 2 bộ đồ chơi xếp hình trong ~n~ bộ, nhóm các ký tự ~A~ và ký tự ~B~ của 2 bộ đã chọn rồi xếp chúng thành một hàng ngang. Ví dụ là có 3 chữ cái ~A~ và 4 chữ cái ~B~ thì ~ABABABB~ và ~BBBBAAA~ là một trong các cách xếp hợp lệ, và ~AAAABBB~ là một trong các cách xếp không hợp lệ.

Via muốn biết: có bao nhiêu cách chọn bộ và xếp chữ như vậy? Hai cách là khác nhau khi hai bộ xếp chữ được chọn ở hai cách là khác nhau, hoặc cách xếp nhận được là khác nhau.

Vì số cách chọn và xếp có thể rất lớn, bạn hãy in ra số cách tìm được chia lấy dư cho ~10^9 + 7~.

Input

Dữ liệu vào từ file văn bản ordletter.inp:

Dòng đầu tiên chứa số nguyên dương ~n~ — là số bộ đồ chơi mà Via được tặng (~2 \le n \le 2 \cdot 10^5~).

~n~ dòng tiếp theo, gồm hai số nguyên ~a_i~ và ~b_i~ — lần lượt là số ký tự ~A~ và số ký tự ~B~ của bộ đồ chơi thứ ~i~ (~1 \le a_i, b_i \le 2000~).

Output

In ra file văn bản ordletter.out một số nguyên duy nhất là số cách chọn bộ và xếp chữ tìm được, modulo ~10^9 + 7~.

Scoring

Subtask Điểm Ràng buộc
~1~ ~10 \%~ ~n \le 5; a_i, b_i \le 10~
~2~ ~20 \%~ ~n \le 2000~
~3~ ~20 \%~ ~a_i, b_i \le 50~
~4~ ~50 \%~ Không có ràng buộc gì thêm

Sample Input 1

2
1 1
2 1

Sample Output 1

10

Comments

Please read the guidelines before commenting.


There are no comments at the moment.