Overview

For each transmitter, we choose either \(V_i\) or \(W_i\). We want to find the number of ways to choose these modes such that the set of values that can be formed by XORing a subset of the chosen \(N\) values contains all the target values \(T_j\).

Since XOR is bitwise addition modulo 2, we can determine this using the concept of a “basis” from linear algebra.

Analysis

Suppose we fix the mode of each transmitter.

Let the values obtained from each transmitter be \(X_1, X_2, \ldots, X_N\). Since we can freely choose any subset of transmitters to operate, the values we can make are all values that can be represented in the form:

\[ X_{i_1} \oplus X_{i_2} \oplus \cdots \oplus X_{i_k} \]

This can be thought of as the XOR linear span of \(X_1, X_2, \ldots, X_N\).

In other words, whether a target value \(T\) can be formed can be determined by checking:

Whether \(T\) can be represented as an XOR linear combination of the chosen values.

---

Naively, one might consider enumerating all \(2^N\) mode choices, and for each choice, enumerating all \(2^N\) subsets to check which XOR sums can be formed.

However, this would take approximately

\[ O(2^N \cdot 2^N) \]

in total, which is too slow even for \(N = 15\).

Instead, we can construct an “XOR basis” for each choice.

Using an XOR basis, we can determine whether a value can be formed in about \(O(60)\) operations. Since the values are less than \(2^{60}\), the maximum number of bits to consider is \(60\).

---

Furthermore, we do not need to check all target values \(T_1, T_2, \ldots, T_M\) every time.

We can construct an XOR basis for the target values themselves.

For example, if a target value can be represented by the XOR sum of other target values, we do not need to check it independently.

If we denote the XOR basis of all target values as \(B_T\), then all \(T_j\) can be formed if and only if the span of the chosen transmitter values contains all basis vectors in \(B_T\).

---

Furthermore, since there are only \(N\) chosen transmitters, the dimension of the space they span is at most \(N\).

Therefore, if the rank of the target values’ XOR basis exceeds \(N\), it is impossible to form all target values.

In this case, the answer is \(0\).

Algorithm

First, we construct an XOR basis from the target values \(T_1, T_2, \ldots, T_M\).

Let the rank of this basis be target_rank.

• If target_rank == 0:
  All target values are \(0\).
  Since \(0\) can always be formed by choosing the empty set, any mode selection satisfies the condition.
  Thus, the answer is \(2^N\).

• If target_rank > N:
  It is impossible because the rank of the XOR space spanned by \(N\) values is at most \(N\).
  Thus, the answer is \(0\).

Otherwise, we search all possible mode selections.

We can represent the mode selection as a bitmask.

• If the \(i\)-th bit of mask is \(0\), transmitter \(i\) is in mode A, i.e., \(V_i\).
• If the \(i\)-th bit of mask is \(1\), transmitter \(i\) is in mode B, i.e., \(W_i\).

For each mask, we construct an XOR basis from the chosen values.

Then, we check if each value in the target basis can be represented by this basis.

If all of them can be represented, this mode selection satisfies the condition, so we add \(1\) to the answer.

---

In the XOR basis, let basis[p] store the “basis vector whose most significant bit (MSB) is \(p\).”

To insert a value \(x\) into the basis, we do the following:

1. Let \(p\) be the most significant bit of \(x\).
2. If basis[p] exists, update \(x \leftarrow x \oplus basis[p]\) to eliminate the most significant bit.
3. If basis[p] does not exist, insert \(x\) at basis[p].
4. If \(x\) becomes \(0\), it is already representable by the basis, so we do not add it.

Checking whether a value \(x\) can be represented by the basis is similar.

We repeatedly eliminate the most significant bits; if we end up with \(0\), it can be represented. If we encounter a bit that cannot be eliminated, it cannot be represented.

Complexity

Let \(B = 60\).

• Time Complexity: \(O\left(MB + 2^N \cdot (N + R)B\right)\)
  Here, \(R\) is the size of the XOR basis of the target values, where \(R \leq 60\).
• Space Complexity: \(O(N + M + B)\)

Since the constraint is \(N \leq 15\), the brute-force search over \(2^N\) states is well within the time limit.

Key Points of Implementation

Since all values are less than \(2^{60}\), an XOR basis array of size \(60\) is sufficient.

basis = [0] * 60

insert_basis returns True if a new value is successfully added to the basis. This allows us to count the rank of the target values.

if insert_basis(target_basis_arr, t):
    target_rank += 1

Also, instead of checking all target values every time, we only need to check the basis of the target values.

target_basis = [x for x in target_basis_arr if x]

This allows us to perform the check efficiently even when \(M\) is up to \(100\).

Source Code

import sys

MOD = 10**9 + 7

def insert_basis(basis, x):
    while x:
        p = x.bit_length() - 1
        if basis[p]:
            x ^= basis[p]
        else:
            basis[p] = x
            return True
    return False

def in_span(basis, x):
    while x:
        p = x.bit_length() - 1
        if basis[p] == 0:
            return False
        x ^= basis[p]
    return True

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0
    N = data[idx]
    M = data[idx + 1]
    idx += 2

    V = [0] * N
    W = [0] * N
    for i in range(N):
        V[i] = data[idx]
        W[i] = data[idx + 1]
        idx += 2

    T = data[idx:idx + M]

    target_basis_arr = [0] * 60
    target_rank = 0
    for t in T:
        if insert_basis(target_basis_arr, t):
            target_rank += 1

    if target_rank == 0:
        print(pow(2, N, MOD))
        return

    if target_rank > N:
        print(0)
        return

    target_basis = [x for x in target_basis_arr if x]

    ans = 0
    for mask in range(1 << N):
        basis = [0] * 60

        for i in range(N):
            x = W[i] if (mask >> i) & 1 else V[i]
            insert_basis(basis, x)

        ok = True
        for t in target_basis:
            if not in_span(basis, t):
                ok = False
                break

        if ok:
            ans += 1

    print(ans % MOD)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.