Bài này thực chất đáp án không to đến mức phải mod ~10^9 + 7~ nhưng để định hướng mọi người nghĩ theo hướng tổ hợp nên cái này được cho vào......

Chu kỳ 6 bóng

• Vì thao tác bật/tắt dựa trên chỉ số bóng theo ~\bmod 2~ (chẵn/lẻ) hoặc ~\bmod 3~ (dạng ~3k+1~), ta có thể kiểm tra dễ thấy rằng trạng thái bóng thứ ~j~ lặp lại khi sang bóng thứ ~j+6~.
• Thực ra chỉ cần xét tới ~n'=\min(n,6)~, và tiếp tục sẽ thấy ~3~ bóng sau hoàn toàn phụ thuộc vào ~3~ bóng đầu.
• Do đó, ta có thể giả sử ~n\le3~. Mỗi trạng thái đèn được xác định bởi vector 3-bit ~(L_1,L_2,L_3)~ với ~L_i\in{0=\text{off},1=\text{on}}~.

Công thức cho 6 bóng đầu

Gọi ~a,b,c,d\in{0,1}~ lần lượt là số dư của việc bấm các nút ~1–4~, tức

• ~a\equiv~ (lần bấm nút 1) mod 2
• ~b\equiv~ (lần bấm nút 2) mod 2
• ~c\equiv~ (lần bấm nút 3) mod 2
• ~d\equiv~ (lần bấm nút 4) mod 2

Vì bấm nút hai lần liên tiếp sẽ hủy nhau (XOR), ta chỉ quan tâm đến ~a,b,c,d~. Ban đầu tất cả sáng ~\equiv1~.

Tính XOR từng nút lên bóng ~i~:

Do đó:

Light1 = 1 ⊕ a ⊕ c ⊕ d  
Light2 = 1 ⊕ a ⊕ b  
Light3 = 1 ⊕ a ⊕ c  
Light4 = 1 ⊕ a ⊕ b ⊕ d  
Light5 = 1 ⊕ a ⊕ c  
Light6 = 1 ⊕ a ⊕ b  

Tại sao chỉ cần 3 bóng đầu

Nhìn vào công thức:

Light5 = 1 ⊕ a ⊕ c
Light3 = 1 ⊕ a ⊕ c

~\Rightarrow~ Rõ là Light5 ~\equiv~ Light3.

Light6 = 1 ⊕ a ⊕ b
Light2 = 1 ⊕ a ⊕ b

~\Rightarrow~ Rõ là Light6 ~\equiv~ Light2.

Đối với Light4, tính tổng ~\pmod{2}~ ba biểu thức của Light1, Light2, Light3:

Light1 ⊕ Light2 ⊕ Light3
=      (1 ⊕ a ⊕ c ⊕ d)
    ⊕ (1 ⊕ a ⊕ b)
    ⊕ (1 ⊕ a ⊕ c)
= 1 ⊕ a ⊕ b ⊕ d = Light4

Vậy bóng ~4,5,6~ hoàn toàn được xác định từ bóng ~1,2,3~.

Trạng thái cả dãy phụ thuộc đầy đủ vào vector 3-bit

~(L_1,L_2,L_3) = (1\oplus a\oplus c\oplus d,1\oplus a\oplus b,1\oplus a\oplus c)~.

Mô hình hóa

Mỗi nút tương ứng với một vector 3-bit ~(m_1,m_2,m_3)~ để XOR vào ~(L_1,L_2,L_3)~:

Các trường hợp

Chúng ta đã thu gọn bài toán về 3 bóng đầu ~(L_1,L_2,L_3)~. Ban đầu ~(1,1,1)~. Mỗi lần bấm là XOR với một trong bốn vector:

$$ v_1 = (1,1,1), v_2 = (0,1,0), v_3 = (1,0,1), v_4 = (1,0,0). $$

~x = 0~

• Không bấm nút nào ~\rightarrow~ không có XOR, giữ nguyên ~(1,1,1)~.
• Chỉ ~1~ trạng thái.

~x = 1~

Bạn chọn 1 trong 4 vector để XOR vào ~(1,1,1)~:

~\rightarrow~ 4 kết quả khác nhau.

• Nếu chỉ quan tâm ~n=1~ bóng đầu ~\rightarrow~ có hai giá trị của ~L_1~ trong tập ~{0,1}~ ~\rightarrow~ ~2~ trạng thái.
• Với ~n=2~ bóng đầu ~\rightarrow~ ta có ba cặp ~(L_1,L_2)~ khác nhau: ~(0,0),;(1,0),;(0,1)~ ~\rightarrow~ ~3~ trạng thái.
• Với ~n=3~ ~\rightarrow~ giữ đủ 3-bit ~\rightarrow~ ~4~ trạng thái.

~x = 2~

Chúng ta cần xét mọi cặp ~{i,j}~ với ~1 \le i \le j \le 4~. Có ~10~ cặp:

Lấy riêng các vector kết quả ở cột cuối và bỏ trùng, ta có:

~{(0,0,0),; (1,0,1),; (0,1,0), (0,1,1), (1,1,1),; (1,1,0), (0,0,1)}~.

Tổng cộng ta thu được ~7~ vector 3‑bit khác nhau.

• Với ~n=1~ ~\rightarrow~ chỉ lấy 1 bit đầu ~\rightarrow~ tối đa 2 trạng thái.
• Với ~n=2~ ~\rightarrow~ chỉ lấy 2 bit đầu, bạn có thể phủ hết ~{00,01,10,11}~ ~\rightarrow~ ~4~ trạng thái.
• Với ~n=3~ ~\rightarrow~ giữ đủ 3-bit ~\rightarrow~ ~7~ trạng thái.

~x \ge 3~

Khi được quyền XOR ít nhất ~3~ lần, ba vector ~v_2,v_3,v_4~ đã là một cơ sở của không gian ~\{0,1\}^3~. Chính vì thế, ta có thể kết hợp để tạo mọi vector 3‑bit (tức cả 8).

• Với ~n\ge3~ ~\rightarrow~ ~8~ trạng thái.
• Với ~n=1~ ~\rightarrow~ vẫn ~2~.
• Với ~n=2~ ~\rightarrow~ vẫn ~4~.

#include <bits/stdc++.h>
using namespace std;

int sol(int n, int x){
    if (x == 0) return 1;
    if (x == 1) return n == 1 ? 2 : n == 2 ? 3 : 4;
    if (x == 2) return n == 1 ? 2 : n == 2 ? 4 : 7;
    return n == 1 ? 2 : n == 2 ? 4 : 8;
}

int main(){
    int t; cin >> t;
    while(t--) {
        int n, x; cin >> n >> x;
        n = min(n, 3);
        cout << sol(n, x) << "\n";
    }
}