켜지고 꺼지는 불빛들

시간 제한1초메모리 제한128 MB

요약

조명 격자에서 k번째 행 옆 버튼을 누르면 바로 위 행과 XOR되고, 임의의 부분집합과 순서로 눌렀을 때 나타날 수 있는 맨 아래 행 패턴의 가짓수를 센다.

난이도: 어려움10점 중 9점
유형: 비트 연산, 수학, 조합론, 행렬
정답자: 아직 제출이 없습니다

문제

$R$ 개의 행( $1 < R < 30$ )으로 이루어진 불빛 격자가 있으며, 각 행에는 $L$ 개의 불빛( $1 \le L < 8$ )이 있습니다. 각 불빛은 켜짐 또는 꺼짐 중 하나의 상태를 가집니다. 가장 위쪽 행이 $R$ 번 행이고, 가장 아래쪽 행이 $1$ 번 행입니다.

가장 위쪽 행( $R$ 번 행)을 제외한 모든 행 옆에는 누를 수 있는 버튼이 하나씩 있습니다. $k$ 번 행( $1 \le k < R$ ) 옆의 버튼을 누를 수 있습니다.

$k$ 번 행 옆의 버튼을 누르면, $k$ 번 행의 각 불빛이 그 바로 위 $k+1$ 번 행의 같은 열 불빛과의 배타적 논리합(XOR)으로 바뀝니다. 구체적으로 열 $i$ ( $1 \le i \le L$ )에 대해, $k$ 번 행과 $k+1$ 번 행의 열 $i$ 불빛이 서로 같으면(둘 다 켜져 있거나 둘 다 꺼져 있으면) $k$ 번 행 열 $i$ 의 불빛은 꺼짐이 되고, 서로 다르면 켜짐이 됩니다.

예를 들어 $L = 4$ 인 경우는 다음과 같습니다.

	열 1	열 2	열 3	열 4
$k+1$ 번 행	켜짐	켜짐	꺼짐	꺼짐
누르기 전 $k$ 번 행	켜짐	꺼짐	켜짐	꺼짐
누른 후 $k$ 번 행	꺼짐	켜짐	켜짐	꺼짐

각 버튼은 최대 한 번만 누를 수 있지만, 버튼을 누르는 순서는 자유롭게 정할 수 있습니다. 버튼을 누르는 모든 가능한 선택과 순서를 통틀어, 가장 아래쪽 행( $1$ 번 행)이 나타낼 수 있는 서로 다른 불빛 패턴이 몇 가지인지 구하세요.

입력

첫째 줄에 행의 개수 $R$ 이 주어집니다. 둘째 줄에 한 행에 있는 불빛의 개수 $L$ 이 주어집니다. 이어지는 $R$ 개의 줄에는 각각 $L$ 개의 정수가 공백 하나로 구분되어 주어지며, $0$ 은 꺼짐, $1$ 은 켜짐을 의미합니다. 이 $R$ 개의 줄은 위에서 아래 순서로 주어집니다. 즉 첫 번째 줄은 $R$ 번 행을, 다음 줄은 $R-1$ 번 행을 나타내며, 마지막 줄이 가장 아래쪽 행( $1$ 번 행)을 나타냅니다.

출력

가장 아래쪽 행이 나타낼 수 있는 서로 다른 불빛 패턴의 개수를 정수 하나로 출력하세요.

예제4

예제 1
입력
```
4
3
0 0 1
0 1 1
1 0 1
0 0 1
```
예상 출력
```
4
```
예제 2
입력
```
2
1
1
0
```
예상 출력
```
2
```
예제 3
입력
```
5
2
1 1
1 1
1 1
1 1
1 1
```
예상 출력
```
2
```
예제 4
입력
```
3
2
0 0
0 0
0 0
```
예상 출력
```
1
```