Submit solution
Points:
0.60 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Ba bé
, và cùng tham gia một trò chơi mang tên "Ba chàng lính ngự lâm". Trò chơi được diễn ra trên bảng ~N\times M~, ba bé sẽ chọn ba ô khác nhau trên bảng sao cho không có người nào có thể đi đến vị trí của người khác bằng một bước di chuyển theo hướng của quân mã trong cờ vua. Hãy đếm số trạng thái khác nhau của trò chơi (hai trạng thái được gọi là khác nhau nếu có ít nhất một người đứng ở hai vị trí khác nhau trong hai trạng thái đó).Input
Dòng đầu tiên chứa một số nguyên dương ~T~ là số bộ test (~T\le 10000~).
~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~N~ và ~M~ (~1 \le N, M \le 10^{9}~) ứng với một bộ test.
Output
Với mỗi truy vấn in ra số trạng thái khác nhau chia lấy dư cho ~10 ^ {9} + 7~.
Subtask
~20\%~ số test có ~T\le 10, 1\le N * M \le 1000~.
~80\%~ số test còn lại không có điều kiện gì thêm.
Sample Input 1
2
2 3
5 4
Sample Output 1
72
3732
Comments