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