Recently, Jimmy is learning about linear algebra from Blue Mary while having the course of Boolean algebra in class offered by Prof. Z. Since Jimmy has been thoroughly bored by the boring homework assigned by two teachers, evil Jimmy plans to set a hard question to baffle them as revenge for their heavy tasks. As a result, Jimmy comes up with an idea that merging the knowledge from both the two classes and constructs a complicate problem: the XOR equation system.
Let’s consider the following equations:
(a11 . x1) ^ (a12 . x2) ^ … ^ (a1m . xm) = 0
(a21 . x1) ^ (a22 . x2) ^ … ^ (a2m . xm) = 0
…
(an1 . x1) ^ (an2 . x2) ^ … ^ (anm . xm) = 0
which satisfies the following conditions:
1. aij in {0,1} for 1 ≤ i ≤ n and 1 ≤ j ≤ m;
2. xi in Si where Si is a subset of {0,1,2,3}, 1 ≤ i ≤ m;
3. |Si| ≤ 3, 1 ≤ i ≤ m;
4. 1≤n ≤ 30, 1 ≤ m ≤ 22.
In the system of equations, operation “ . “ denotes the multiplication operation while “ ^ ” is for bitwise XOR. Moreover, the bitwise XOR takes two bit patterns of equal length and performs the logical XOR operation on each pair of corresponding bits. The result in each position is 1 if the two bits are different, and 0 if they are the same.
Rather than expecting a solution of a specified equation system, Jimmy would like to ask the teachers to calculate that how many distinct solutions can satisfy a given equation system. What a confusing puzzle! Help Jimmy’s teachers please!