TLEoj Contest #03 - Đếm ma trận - TLEOJ: TLE Online Judge

TLEoj Contest #03 - Đếm ma trận

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

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

huyhau6a2

Dạng bài

Bạn được cho một ma trận $n\times m$ . Với mỗi ô $(i,j)$ trong ma trận có thể sẽ có giá trị $0$ hoặc $1$ .

huyhau6a2 thực hiện 1 trò chơi trong ma trận như sau. Ban đầu bạn sẽ ở vị trí $(1,1)$ . Từ ô $(i,j)$ bạn có thể đi đến 1 trong 2 ô $(i+1,j)\ (i<n)$ hoặc $(i,j+1)\ (j<m)$ . Dễ dàng nhận thấy sau 1 số bước ta sẽ đến được ô $(n,m)$ . Ta gọi giá trị của đường đi từ ô $(x_1,y_1)$ đến ô $(x_2,y_2)$ là tổng $XOR$ của tất cả giá trị trên đường đi (tính cả ô xuất phát và ô kết thúc).

Trong đó, $XOR$ là phép toán bit xor. Bạn có thể đọc tại đây

Với một ma trận kích thước $n\times m$ , ta gọi ma trận đó là ma trận đẹp nếu với mọi đường đi hợp lệ từ ô $(1,1)$ đến ô $(n,m)$ thì giá trị của các đường đi đó đều bằng $1$

Nhiệm vụ của bạn là hãy đếm số cách điền các giá trị $0$ hoặc $1$ vào ma trận sao cho ma trận đó là ma trận đẹp. Vì kết quả có thể rất lớn nên hãy xuất kết quả sau khi $mod\ 10^9+7$

Input, Output và Subtasks

Input

Dòng thứ nhất gồm 1 số $t$ là số testcase ( $1\le t\le 10$ )
Sau đó là $t$ dòng, mỗi dòng nhập 2 số $n,m$ ( $1\le n,m\le 10^{18}$ )

Output

Xuất ra $t$ dòng, mỗi dòng gồm 1 số tương ứng với kết quả từng testcase.

Scoring

Subtask 1 ( $20\%$ ): $n,m\le 4$
Subtask 2 ( $20\%$ ): $n=1$ hoặc $m=1$
Subtask 3 ( $20\%$ ): $n,m\le 1000$
Subtask 4 ( $20\%$ ): $n,m\le 10^6$
Subtask 5 ( $20\%$ ): Không có ràng buộc gì thêm

Sample

Input

Output

1
2
4

Note

Trong test ví dụ đầu tiên, có 1 ma trận đẹp thỏa mãn là:

Example 1

Trong test ví dụ thứ hai, có 2 ma trận đẹp thỏa mãn là:

Example 2

Trong test ví dụ cuối cùng, có 4 ma trận đẹp thỏa mãn là:

Example 3

10
00

00
01

01
10

11
11

Bình luận

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