Problem Description

Snuke wrote two different integers \( X \) and \( Y \) on the blackboard, along with a \( K \times K \) grid. Then, he wrote an integer \( A_{i,j} \) in each cell of the grid.

Snuke decided to call a sequence \( a \) of length \( K \) good if it satisfies the following condition:

• For any \( (i,j) \) such that \( 1 \leq i, j \leq K \), the following holds:
• \( a_i \text{ xor } a_j \text{ xor } X \) or \( a_i \text{ xor } a_j \text{ xor } Y \) equals \( A_{i,j} \).
• Here, \( \text{xor} \) denotes the bitwise exclusive OR operation.

Snuke has \( N \) integers, where the \( i \)-th integer is \( x_i \). He decided to choose \( K \) of these integers to form a sequence of length \( K \). How many of the sequences he can form are good? Find the answer modulo \( 10^9 + 7 \).

Note that there may be multiple ways to arrange the numbers to form the same sequence, but these are not distinguished. Refer to Sample 1 for more details.

Input Format

The input is given from the standard input in the following format:

\( N \) \( K \) \( X \) \( Y \) \( x_1 \) \( ... \) \( x_N \) \( A_{1,1} \) \( ... \) \( A_{1,K} \) \( : \) \( A_{K,1} \) \( ... \) \( A_{K,K} \)

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

6 3 1 0
0 8 1 2 15 8
1 2 8
2 0 10
8 10 1

Sample Output #1

2

Sample Input #2

2 2 0 4
0 1
8 16
110 12

Sample Output #2

0

Sample Input #3

35 4 11 1
23 2 17 16 22 22 6 0 0 15 16 5 12 21 0 9 17 0 2 26 22 19 6 16 13 7 26 8 22 29 26 13 8 32 14
1 0 15 31
0 11 14 20
5 4 1 17
21 20 27 1

Sample Output #3

26

Notes/Hints

Constraints

• \( 1 \leq N \leq 2048 \)
• \( 1 \leq K \leq \min(1024, N) \)
• \( 0 \leq X, Y, x_i, A_{i,j} < 2048 \)
• \( X \neq Y \)
• All given inputs are integers

Sample Explanation 1

• The possible sequences are \( (0, 2, 8) \) and \( (1, 2, 8) \), totaling 2 sequences. Note that there are 2 ways to arrange the numbers to form \( (0, 2, 8) \), but these are not distinguished.

Sample Explanation 2

• No sequence can satisfy the condition.

见题面 Input 部分

见题面 Output 部分