Given an array (a_1, a_2, \ldots, a_n) and three variables (P, Q, R) initially set to zero, process each element sequentially. For each element (a_i), choose one of three operations:

1. (P := P \oplus a_i)
2. (Q := Q \oplus a_i)
3. (R := R \oplus a_i)

After each operation, at least two of (P, Q, R) must be equal. The task is to count the number of valid operation sequneces modulo (10^9 + 7).

Input Format

The input consists of multiple test cases. The first line contains the number of test cases (t). Each test case includes:

• An integer (n) (array length)
• (n) integers (a_1, a_2, \ldots, a_n)

Output Format

For each test case, output the count of valid sequences modulo (10^9 + 7).

Solution Approach

Use dynamic programming with a segment tree to track valid states efficiently. The key observation is that the XOR sum of the array elements determines the unique value among (P, Q, R) at each step.

Code Example

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

const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;

struct SegmentTree {
    struct Node { int left, right, sum; };
    vector<Node> nodes;
    int root, nextId;

    SegmentTree() : root(0), nextId(1) { nodes.resize(1); }

    void update(int &id, int l, int r, int pos, int val) {
        if (!id) {
            id = nextId++;
            nodes.emplace_back();
        }
        if (l == r) {
            nodes[id].sum = (nodes[id].sum + val) % MOD;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(nodes[id].left, l, mid, pos, val);
        else update(nodes[id].right, mid + 1, r, pos, val);
        nodes[id].sum = (nodes[nodes[id].left].sum + nodes[nodes[id].right].sum) % MOD;
    }

    int query(int id, int l, int r, int pos) {
        if (!id) return 0;
        if (l == r) return nodes[id].sum;
        int mid = (l + r) >> 1;
        return pos <= mid ? query(nodes[id].left, l, mid, pos) : query(nodes[id].right, mid + 1, r, pos);
    }

    void clear() {
        root = 0;
        nextId = 1;
        nodes.clear();
        nodes.emplace_back();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int &x : a) cin >> x;

        SegmentTree st;
        st.update(st.root, 0, 1 << 30, 0, 1);
        int xorSum = 0;

        for (int x : a) {
            int val = (st.query(st.root, 0, 1 << 30, xorSum ^ x) + st.query(st.root, 0, 1 << 30, xorSum)) % MOD;
            st.update(st.root, 0, 1 << 30, xorSum, 2 * val % MOD);
            xorSum ^= x;
        }
        cout << st.nodes[st.root].sum << '\n';
    }
    return 0;
}