준혁이의 자취방 꾸미기

준혁이는 지난 학기부터 자취를 시작했다. 한 학기를 혼자 지낸 준혁이는 여름이 되자 자취방에 있는 $N$개의 창문으로 들어오는 햇살이 너무 강하고 더워서, 창문을 꾸며 여름을 나기로 했다.

준혁이는 자취 경험이 많은 선배 동우에게 도움을 청했다. 후배의 부탁이므로 동우는 자신이 연구한 창문에 대한 정보를 알려주기로 했다. 동우는 대학에서 선형대수 과목을 무려 5개나 들었을 정도로 선형대수를 좋아해서, 창문도 행렬로 분석한다. 동우는 창문을 알려면 먼저 행렬 곱과 텐서 곱을 이해해야 한다고 말했다.

• 행렬 $X$의 $i$행 $j$열 원소를 $x_{i,j}$로 쓴다. 같은 알파벳 소문자에 아래첨자를 붙인 것이다.

• 행렬 곱

  • $n\times m$ 행렬 $A$와 $k\times l$ 행렬 $B$에 대해 행렬 곱은 $m=k$일 때만 가능하며, 결과 $C=AB$는 $n\times l$ 행렬이다.
  • $C$의 $i$행 $j$열 원소는 $A$의 $i$행 행벡터와 $B$의 $j$열 열벡터의 내적이다. 즉, 대응하는 위치의 원소끼리 곱해 더한 값이다.
  • 구체적으로 $c_{i,j}=\displaystyle\sum_{t=1}^{m}a_{i,t}b_{t,j}$이다.
  • 행렬 곱은 교환법칙이 성립하지 않지만 결합법칙은 성립한다.
  • 예를 들어 $\left[ \begin{matrix}1& 2\\ 3& 4\end{matrix} \right]\left[ \begin{matrix}5& 6\\ 7& 8\end{matrix} \right] =\left[ \begin{matrix}1\cdot 5+2\cdot 7& 1\cdot 6+2\cdot 8\\ 3\cdot 5+4\cdot 7& 3\cdot 6+4\cdot 8\end{matrix} \right] =\left[ \begin{matrix}19& 22\\ 43& 50\end{matrix} \right]$이다.

• 텐서 곱($\otimes$)

  • $n\times m$ 행렬 $A$와 $k\times l$ 행렬 $B$에 대해 텐서 곱 $C=A\otimes B$는 $nk\times ml$ 행렬이다.
  • 행렬 $A$의 각 원소 $a_{i,j}$ 자리에 $a_{i,j}B$를 적은 모양이다.
  • 구체적으로 $c_{i,j}=a_{\lfloor i/k\rfloor ,\lfloor j/l\rfloor}b_{(i \bmod k),(j \bmod l)}$이다.
  • 텐서 곱은 교환법칙이 성립하지 않지만 결합법칙은 성립한다.
  • 예를 들어 $\left[ \begin{matrix}1& 2\\ 3& 4\end{matrix} \right]\otimes\left[ \begin{matrix}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{matrix} \right] =\left[ \begin{matrix}1& 2& 3& 2& 4& 6\\ 4& 5& 6& 8& 10& 12\\ 7& 8& 9& 14& 16& 18\\ 3& 6& 9& 4& 8& 12\\ 12& 15& 18& 16& 20& 24\\ 21& 24& 27& 28& 32& 36\end{matrix} \right]$이다.

• 벡터의 텐서 곱

  • $n$차원 벡터의 열벡터는 $n\times 1$, 행벡터는 $1\times n$ 행렬로 보고 계산할 수 있다.
  • '열' 또는 '행'이 붙지 않은 벡터는 일반적으로 열벡터를 뜻한다.
  • 전치($\top$)를 붙이면 열벡터는 행벡터가, 행벡터는 열벡터가 된다.
  • 예를 들어 $\left[ \begin{matrix}1\\ 2\\ 3\\ 4\end{matrix} \right]\otimes\left[ \begin{matrix}5\\ 6\end{matrix} \right] =\left[ \begin{matrix}5& 6& 10& 12& 15& 18& 20& 24\end{matrix} \right]^\top$이다.

각 창문은 순서가 정해진 $M$개의 2차원 벡터로 표현할 수 있다. 준혁이의 방을 둘러본 동우는 $N$개의 창문이 현재 각각 $M$개의 $\left[ \begin{matrix}1\\ 2\end{matrix} \right]$로 이루어져 있음을 알아냈다. 동우는 창문마다 이 벡터들로 정해지는 "채광도"가 있고, 이 값으로 창문을 통해 들어오는 햇빛의 양을 조절할 수 있다고 알려주었다. 채광도는 $2^M$차원 벡터이며, 창문을 구성하는 $M$개의 2차원 벡터를 순서대로 텐서 곱한 것으로 정의된다. 즉, 창문을 구성하는 벡터가 $V_1$, $V_2$, $\cdots$, $V_M$이고 $V_i=\left[ \begin{matrix}V_{1i}\\ V_{2i}\end{matrix} \right]$이라면(위의 일반적인 행렬 표기와 다르므로 유의한다), 채광도는 $L=V_1\otimes V_2\otimes V_3\otimes\cdots\otimes V_M$이다.

또한 채광도를 조정하기 위해 인부를 부를 수 있다. 각 인부는 순서가 정해진 $M$개의 $2\times 2$ 행렬로 표현된다. 이 행렬은 다음 네 개 중 하나이다. $\left[ \begin{matrix}1& 0\\ 0& 1\end{matrix} \right]$, $\left[ \begin{matrix}0& 1\\ 1& 0\end{matrix} \right]$, $\left[ \begin{matrix}0& 1\\ -1& 0\end{matrix} \right]$, $\left[ \begin{matrix}1& 0\\ 0& -1\end{matrix} \right]$. 인부에게는 "특성"이 있으며, 특성은 인부를 표현하는 $M$개의 행렬을 순서대로 텐서 곱한 $2^M\times 2^M$ 행렬이다.

총 $K$일 동안 날마다 꾸밀 수 있는 창문들이 있다. 준혁이는 날마다 인부 한 명을 불러 그날 꾸밀 수 있는 창문을 모두 꾸민다. 인부는 그날 꾸밀 수 있는 창문을 반드시 모두 꾸며야 하며, 그 밖의 창문은 꾸미지 않는다.

인부가 작업한 창문의 채광도는, 인부의 특성을 나타내는 $2^M\times 2^M$ 행렬과 창문의 기존 채광도인 $2^M$차원 벡터의 행렬 곱으로 바뀐다.

마지막 인부의 작업이 끝난 후 준혁이는 $N$개 창문의 채광도 각각에 $-1$을 곱하거나 곱하지 않을 수 있다.

준혁이가 원하는 $N$개 창문의 채광도가 주어질 때, 최종적으로 모든 창문의 채광도를 원하는 대로 만들도록 날마다 인부를 정하는 방법의 수를 구하라. 인부는 행렬의 종류나 순서가 하나라도 다르면 다른 인부로 보고, 행렬의 종류와 순서가 모두 같으면 같은 인부로 본다. 또한 $K$일 동안 부른 인부의 순서가 다르면 다른 방법으로 보아 각각 한 번씩 센다.

인부는 가능한 모든 행렬 조합에 대해 존재하며, 같은 인부를 여러 번 불러도 된다.

첫째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. ($1\le N\le 1\,000$, $1\le M\le 1\,000$, $1\le K\le 1\,000$)

다음 $N$개의 줄에는 1번째부터 $N$번째 창문에 대해 준혁이가 최종적으로 원하는 채광도 $V_{11}$, $V_{12}$, ..., $V_{M1}$, $V_{M2}$($-1\,000\le V_{ij}\le 1\,000$)가 한 줄에 하나씩 공백으로 구분되어 주어진다.

다음 $K$개의 줄에는 1일부터 $K$일까지 꾸밀 수 있는 창문의 종류가 한 줄에 하나씩 주어진다. 각 줄은 먼저 그날 꾸밀 수 있는 창문의 개수 $P$가 주어지고, 이어서 창문의 번호 $W_1$, $W_2$, ..., $W_P$($1\le W_1<W_2<\cdots<W_P\le N$)가 공백으로 구분되어 주어진다.

준혁이가 원하는 창문 상태를 달성하도록 날마다 인부를 정하는 방법의 수를 $10^9+7$로 나눈 나머지를 출력한다.