| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P157PROF - ROUND 7F - Quân mã |
Bài toán đặt các quân Mã trong bàn cờ đã khá quen thuộc trong Toán Tin. Bây giờ chúng ta mở rộng bài toán với một bàn cờ hình chữ nhật có M hàng, N cột.
Hãy đếm số cách có thể đặt các quân Mã trên bàn cờ sao cho không con nào ăn được con nào (tính cả trường hợp không đăt quân nào lên bàn cờ). Hai cách sắp xếp các con Mã được coi là khác nhau nếu tồn tại một ô có chứa con Mã ở cách thứ nhất nhưng không có con Mã trong cách thứ 2.
Input
Dòng đầu tiên ghi số bộ test (không quá 10).
Mỗi bộ test ghi lần lượt 2 số M và N. (1 <=M <=4; 1 <= N <=109).
Output
Với mỗi bộ test, ghi ra số cách tính được. Nếu số cách quá lớn thì chia phần dư cho 1000000009 (109 + 9).
Example
Input:
Output:41 22 23 24 3141592641636413011760
| Được gửi lên bởi: | adm |
| Ngày: | 2015-04-12 |
| Thời gian chạy: | 30s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
