Những quân xe đủ màu

View as PDF

Submit solution

Points: 1.74 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
SRM 473, Div 1 - Level 3Người dịch: Ngô Minh Ðức
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một bàn cờ và các quân xe nhiều màu khác nhau. Hãy đếm số cách sắp xếp tất cả các quân xe lên bàn cờ sao cho không có hai con xe khác màu nào được tấn công lẫn nhau.

Input

Dữ liệu

  • Mỗi test bắt đầu bằng thẻ "[CASE]", các test cách nhau bởi một dòng trắng. Thẻ "[END]" báo hiệu kết thúc file input.
  • Hai dòng tiếp theo là M, N, kích thước của bàn cờ
  • Tiếp theo là dòng "~<$$<~".
  • Các dòng tiếp theo, mỗi dòng chứa số lượng quân xe của một màu.
  • Kết thúc bằng dòng "~>$$>~'.

Output

Kết quả

  • Với mỗi test, trả về phần dư của kết quả cho ~1\,000\,000\,009~.

Giới hạn

  • ~1 \le M~, ~N \le 30~
  • Có từ ~1~ đến ~10~ màu phân biệt.
  • Tổng số quân xe không quá ~M \times N~.

Sample Input

[CASE]
2
3
<<
1
1
>>

[CASE]
5
2
<<
3
>>

[CASE]
5
2
<<
1
1
1
>>

[CASE]
8
8
<<
1
1
1
1
1
1
1
1
>>


[CASE]
4
2
<<
3
1
>>

[END]

Sample Output

12
120
0
625702391
8

Comments

Please read the guidelines before commenting.


There are no comments at the moment.