소등 시간

하늘이의 생활관은 구조가 독특해서, 소등 시간마다 하늘이가 불을 끄는 데 어려움을 겪고 있다.

생활관에는 전구가 $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$은 꺼져 있는 상태를 의미한다.

첫째 줄에 조건을 만족하며 소등하는 방법의 수를 출력한다.