入门数学

题目描述

我们有一个$n$行$m$列的矩阵$A$，第$i$行第$j$列的数记作$A_{i,j}$。同时给定了一个长度为$m$的序列$x$。

定义一个长度为$k$（$1 \leq k \leq n$）的整数序列$p$是"好"的，当且仅当其满足如下条件：

• 序列中每个数均满足$1 \leq p_i \leq n$；
• 若$i \neq j$，则$p_i \neq p_j$；
• $\forall 1 \leq i \leq m$，$A_{p_1,i} \oplus A_{p_2,i} \oplus \cdots \oplus A_{p_k,i} = x_i$（其中$\oplus$为一种位运算：$\&$是与，$|$是或，$\wedge$是异或）。

现在给定$A$和$x$以及$\oplus$，请你求出有多少满足条件的序列$p$。

两个序列不同，当且仅当它们的长度不同，或者存在一个位置不同。

这个答案可能很大，请你求出对$10^{9}+9$取模的结果。

输入格式

第$1$行一个字符$\oplus$和两个整数$n$，$m$，如题目中描述。

第$2$到$n+1$行每行$m$个数表示$A$。

第$n+2$行$m$个数表示$x$。

输出格式

输出一行一个整数表示答案。

数据范围与提示

本题采用子任务捆绑测试。对于每个子任务，你只有通过了这个子任务的所有测试点，才能获得这个子任务的分数。

• 子任务$1$（$10$分）：$n$，$m \leq 7$；
• 子任务$2$（$10$分）：$n$，$m \leq 10$；
• 子任务$3$（$5$分）：$\oplus = \&$；
• 子任务$4$（$5$分）：$\oplus = |$；
• 子任务$5$（$5$分）：$\oplus = \wedge$；
• 子任务$6$（$20$分）：$n$，$m \leq 15$；
• 子任务$7$（$30$分）：$n$，$m \leq 20$；
• 子任务$8$（$15$分）：无特殊限制。

对于$100\%$的数据，$1 \leq n$，$m \leq 25$，$A_{i,j}$，$x_i \in \{0,1\}$。

样例

& 5 4
1 0 1 0 
1 1 1 0 
0 1 1 1 
0 1 1 0 
1 0 1 1 
0 1 1 0 

13

| 5 4
1 0 0 0 
0 0 0 1 
0 1 1 0 
0 1 0 1 
0 0 0 1 
0 1 0 1  

11

^ 6 4
1 1 1 0 
1 0 1 1 
1 1 0 0 
1 1 0 1 
0 1 1 0 
1 1 0 0 
1 1 0 0 

50