준혁이의 자취방 꾸미기

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

준혁이는 자취 마스터인 동우에게 도움을 요청했고, 동우는 후배의 부탁인 만큼 본인이 연구한 창문에 대한 정보를 알려주기로 했다. 동우는 대학교에서 선형대수를 배우는 과목을 무려 5개나 수강하였을 정도로 선형대수를 좋아하기 때문에 창문 역시 행렬로 분석하였다. 동우는 창문을 알기 위해 먼저 행렬 곱과 텐서 곱에 대한 이해가 필요하다고 했다.

행렬 $X$ 의 $i$ 행 $j$ 열을 $x\_{i,j}$ 로 표기한다. 즉, 같은 알파벳 소문자에 아래첨자를 붙인다.
행렬 곱
- $n\times m$ 차원 행렬 $A$ 와 $k\times l$ 차원 행렬 $B$ 에 대해 행렬 곱은 $m=k$ 일 때만 가능하며, $n\times l$ 차원 행렬 $C=AB$ 이 된다.
- $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$ 에 대해 행렬 곱은 $nk\times ml$ 차원 행렬 $C=A\otimes B$ 이 된다.
- 텐서 곱은 원래 행렬 $A$ 의 $a\_{i,j}$ 자리에 $a\_{i,j}B$ 의 행렬을 적은 모양이다.
- 즉, $C$ 의 $i$ 행 $j$ 열은 $A$ 의 ( $i$ 를 $k$ 로 나눈 몫 + $1$ )행 ( $j$ 를 $l$ 로 나눈 몫 + $1$ )열의 원소와 $B$ 의 ( $i$ 를 $k$ 로 나눈 나머지 + $1$ )행 ( $j$ 를 $l$ 로 나눈 나머지 + $1$ )열의 원소의 곱이다.
- 구체적으로 $c\_{i,j}=a\_{\lfloor i/k\rfloor ,\lfloor j/l\rfloor}b\_{\left( i\bmod k \right) ,\left( j\bmod l \right)}$ 가 된다.
- 텐서 곱은 교환법칙은 성립하지 않고 결합법칙은 성립한다.
- 예를 들어 $\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$ 차원 벡터들을 순서대로 텐서 곱한 것으로 정의된다. 즉, 각 창문을 구성하는 $M$ 개의 벡터가 $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$ 일 동안 부른 인부 혹은 순서가 다르면 방법이 다른 것으로 생각해 각각 한 번씩 센다.

인부는 가능한 모든 행렬의 조합에 대해 존재하고, 같은 인부가 중복되어도 상관없다.

준혁이의 자취방 꾸미기

문제

입력

출력