TLEoj Contest #11 - Cờ vua - TLEOJ: TLE Online Judge

TLEoj Contest #11 - Cờ vua

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

Thời gian: 0.5s

Bộ nhớ: 16M

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

Lại là $1$ bài toán khác về cờ vua.

Hôm nay là một ngày đẹp trời, flo, Noobcoder và mondellbit009 quyết định đến nhà của flo để chơi cờ vua $4$ người bởi cả $3$ rất thích chơi cờ vua.

Sau khi chơi $69420$ ván cờ vua, cả $3$ đã bắt đầu thấy chán chơi cờ vua thông thường. Thế là flo quyết định lấy bàn cờ vua với kích thước $n \times m$ mà mondellbit009 tặng cậu vào sinh nhật cùng với những con mã của Noobcoder. Trong lúc suy nghĩ nên chơi gì với những món này thì bỗng một bài toán khá thú vị xuất hiện trong đầu của flo.

Nội dung bài toán

Cho một bàn cờ gồm $n$ hàng, $m$ cột và một quân mã nằm ở ô $(1, 1)$ . Tại mỗi bước, quân mã chỉ có thể di chuyển từ ô $(i, j)$ sang ô $(i+1, j+2)$ hoặc $(i+2, j+1)$ và không được rời khỏi bàn cờ. Nhiệm vụ của bạn là đếm số lượng cách đi từ ô $(1, 1)$ đến ô $(n, m)$ .

Bài toán trên quá dễ nên flo, Noobcoder và mondellbit009 đã giải nó chỉ trong $69420ms$ . Vậy nên bạn hãy thử sức với bài toán trên nhé.

Input, Output and Scoring

Input

Số nguyên dương $t$ $(1 \le t \le 10^5)$ .
$t$ dòng tiếp theo, mỗi dòng gồm $2$ số nguyên dương $n, m$ $(1 \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 $2^{32}-3$ .

Scoring

Subtask $1$ $(20\%)$ : $1 \le n, m \le 10^3$ .
Subtask $2$ $(30\%)$ : $1 \le n, m \le 10^6$ .
Subtask $3$ $(50\%)$ : Không giới hạn gì thêm.

Example

Input

Output

1
0
4

Note

Không có gì đâu

Bình luận

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