28260번 - 초콜릿의 맛은 몇 점?

문제

코코는 $R\times C$ 크기의 직사각형 모양 초콜릿을 생산하는 공장을 운영하고 있다. 초콜릿은 1ドル\times 1$ 크기의 단위 초콜릿으로 나누어져 있으며, 각각의 단위 초콜릿의 맛은 하나의 양의 정수로 나타낼 수 있다.

최근 연구에 따르면, 초콜릿의 맛은 초콜릿의 모든 부분 폴리오미노의 맛의 합이라고 한다. 폴리오미노란 하나 이상의 단위 초콜릿을 변끼리 이어붙인 모양을 뜻하며, 폴리오미노의 맛은 폴리오미노에 속한 모든 단위 초콜릿의 맛을 XOR한 값이다.

코코는 자신의 공장에서 생산되는 초콜릿들의 맛이 몇 점인지 궁금해졌다. 코코의 궁금증을 해결해주자.

입력

첫 줄에는 $R,ドル $C$의 값이 주어진다. (1ドル\le R\times C\le 29$)

다음 $R$개 줄에 걸쳐서, 각 단위 초콜릿의 맛의 값이 주어진다. $i$번째 줄의 $j$번째 수는 위에서부터 $i$번째 줄, 왼쪽에서부터 $j$번째 칸에 위치한 단위 초콜릿의 맛을 나타낸다. 단위 초콜릿의 맛은 1ドル$ 이상 10ドル^6$ 이하이다.

출력

주어진 초콜릿의 맛의 값을 한 줄에 출력한다.

제한

노트

음이 아닌 두 정수 $a$와 $b$의 XOR은 $a\oplus b$라고 쓰고, 그 정의는 다음과 같다.

• $a$와 $b$를 같은 길이의 2진법으로 표현했을 때 둘의 $i$번째 자리가 같으면 $a\oplus b$의 2진법 표현의 $i$번째 자리는 0ドル$이고, 서로 다르면 1ドル$이다. 2진법으로 표현했을 때 길이가 서로 다르면, 짧은 쪽의 앞에 0을 필요한 만큼 덧붙인 후 계산한다.

C, C++, Python 등의 프로그래밍 언어에서 $a$와 $b$의 XOR은 a^b로 표현한다.

여러 개의 음이 아닌 정수 $a_1,a_2,\cdots ,a_n$의 XOR은 앞에서부터 순서대로 XOR을 계산한 결과, 즉 $((a_1\oplus a_2)\oplus\cdots)\oplus a_n$과 같다.