Bedao Mini Contest 14 - MUSKETEERS

View as PDF

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é Naot, lastPledgeLeThanhMinh 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

Please read the guidelines before commenting.


There are no comments at the moment.