Cờ vua

Điểm: 2700 (thành phần)

Thời gian: 0.2s

Python 3 2.0s

Bộ nhớ: 512M

Input: bàn phím

Output: màn hình

Tác giả:

flo

Dạng bài

Ngôn ngữ cho phép

C++, ~~NASM~~, Pascal, pypy3, Python

Bài đầu tiên của flo và đây là phiên bản reupload :D

Sau một ngày dài mệt mỏi, flo quyết định chơi cờ vua với bạn cậu là huyhau6a2 để xả stress.

Sau khi chơi $69420$ ván cờ, flo và huyhau6a2 đã bắt đầu chán chơi cờ theo kiểu bình thường. Thế là cả hai quyết định dùng bàn cờ $n\times m$ vừa mua ở Ohio ra chơi. Nhà của flo có rất nhiều quân mã nên cả hai lấy ra để nghịch. Sau đó, flo vô tình phát hiện ra một bài toán vô cùng thú vị và độc đáo như sau.

Nội dung bài toán

Trên bàn cờ $n \times m$ , có một quân mã nằm ở ô $(1, 1)$ . Hãy tính số nước đi tối thiểu để di chuyển quân mã đó đến ô $(i, j)$ .

Bài toán như vậy thì khá là dễ nên flo đã giải chỉ trong vòng $1$ nốt nhạc. Vậy là cậu đã nghĩ ra phiên bản khó hơn như sau.

Nội dung bài toán

Gọi $F(n, m) = \sum_{i = 3}^{n} \sum_{j = 3}^{m} K(i, j)$ với $K(i, j)$ là hàm để tính số nước đi tối thiểu để di chuyển quân mã từ ô $(1, 1)$ đến ô $(i, j)$ . Cho $2$ số nguyên dương $n, m$ , hãy tính $F(n, m)$ .
Một quân mã chỉ có thể di chuyển từ ô $(i, j)$ sang ô $(i+2, j+1),$ $(i+2, j-1),$ $(i-2, j+1),$ $(i-2, j-1),$ $(i+1, j+2),$ $(i-1, j+2),$ $(i+1, j-2),$ $(i-1, j-2)$ và không được rời khỏi bàn cờ.

Cả flo và huyhau6a2 rất muốn biết đáp án. Tuy nhiên, cả hai đang rất là mệt mỏi. Là một con người tốt bụng, bạn hãy giúp flo và huyhau6a2 tìm đáp án nhé.

Input, Output và Scoring

Input

Số nguyên dương $t$ $(1 \le t \le 2 \times 10^4)$ .
$t$ dòng tiếp theo, mỗi dòng gồm $2$ số nguyên dương $n, m$ $(3 \le n, m \le 10^{18})$ .

Output

Với mỗi dòng, hãy in ra kết quả sau khi chia lấy dư cho $10^9+7$ .

Scoring

Subtask $1$ $(10\%)$ : $t = 1; 3 \le n, m \le 10^3$ .
Subtask $2$ $(10\%)$ : $1 \le t \le 2 \times 10^4; 3 \le n, m \le 10^3$ .
Subtask $3$ $(10\%)$ : $t = 1; 3 \le n, m \le 10^6$ .
Subtask $4$ $(10\%)$ : $1 \le t \le 2 \times 10^4; 3 \le n, m \le 10^6$ .
Subtask $5$ $(15\%)$ : $t = 1; 3 \le n, m \le 10^{12}$ .
Subtask $6$ $(15\%)$ : $1 \le t \le 2 \times 10^4; 3 \le n, m \le 10^{12}$ .
Subtask $7$ $(15\%)$ : $t = 1; 3 \le n, m \le 10^{18}$ .
Subtask $8$ $(15\%)$ : $1 \le t \le 2 \times 10^4; 3 \le n, m \le 10^{18}$ .

Example

Input

2
10 12
5 9

Output

390
74

Bình luận

Không có bình luận nào.