33281번 - 소등 시간

문제

하늘이의 생활관은 구조가 독특하여 소등 시간마다 소등에 어려움을 겪고 있다.

하늘이의 생활관에는 전구가 $N\times M$ 격자 모양으로 가지런히 설치되어 있다. 즉 행이 $N$개이고 열이 $M$개여서 총 $NM$개의 전구가 있다.

전구를 켜고 끌 수 있는 스위치는 $N$개가 있는데, $i$번째 스위치는 $i$번째 행의 모든 전구의 상태를 반전시킨다$(1\le i\le N)$. 즉 켜져 있었으면 꺼지고, 꺼져 있었으면 켜진다.

하늘이는 처음 전구가 켜져 있는 상태에 따라서 모든 전구를 끄는 것은 불가능할 수도 있다는 것을 깨달았다. 따라서 각 열마다 최대 한 개의 전구까지는 켜져 있어도 모른척 하기로 했다.

하늘이의 생활관 전구의 초기 상태가 주어질 때, 조건에 맞게 소등하는 경우의 수를 구하시오.

입력

첫째 줄에 $N$과 $M$이 공백을 사이에 두고 주어진다. $(1\le N,M\le 3,円 000)$

둘째 줄부터 $N$개의 줄에 걸쳐 전구의 초기 상태를 나타내는 길이 $M$의 문자열이 주어진다. 1ドル$은 켜져 있는 상태를, 0ドル$은 꺼져 있는 상태를 의미한다.

출력

첫째 줄에 조건에 맞게 소등하는 경우의 수를 출력한다.

제한

힌트