로봇 게임

(참고: 대회 제한 시간은 3초였습니다. 더 많은 풀이가 통과할 수 있도록 여기서는 더 큰 제한 시간을 설정했습니다.)

$m$ 대 ($1 \le m \le 1000$)의 로봇과 $m$ 개의 테이프가 있습니다. $i$ 번째 로봇 ($1 \le i \le m$)은 테이프 $i$ 를 다룹니다. 각 테이프는 왼쪽에서 오른쪽으로 $n$ 개 ($1 \le n \le 32$)의 칸으로 나뉘며, 칸에는 $0, 1, \dots, n-1$ 번호가 붙어 있습니다. 각 칸은 다음 세 가지 상태 중 하나입니다. (1) 숫자 0이 적혀 있다, (2) 숫자 1이 적혀 있다, (3) 비어 있다.

로봇은 언제나 테이프의 어느 한 칸 위에 있어야 합니다. 로봇을 테이프의 초기 위치에 놓은 뒤, $i$ 번째 로봇은 정해진 연산열 $S_i$ 를 실행합니다. 연산은 R, 0, 1, * 문자로 이루어집니다.

• R은 로봇을 한 칸 오른쪽으로 이동시킵니다. 오른쪽에 칸이 없으면 로봇은 폭발합니다.
• 0은 현재 칸이 비어 있지 않으면 그 칸의 숫자를 0으로 바꿉니다. 비어 있으면 칸을 바꾸지 않습니다.
• 1은 현재 칸이 비어 있지 않으면 그 칸의 숫자를 1로 바꿉니다. 비어 있으면 칸을 바꾸지 않습니다.
• *는 현재 칸이 비어 있지 않으면 숫자 $x$ 를 $1-x$ 로 뒤집습니다. 비어 있으면 칸을 바꾸지 않습니다.

$i$ 번째 테이프의 상태는 길이 $n$ 의 문자열로 나타냅니다. 각 문자는 0, 1, - (빈 칸) 중 하나입니다. 테이프 $i$ 의 초기 상태가 입력 $X_i$ 이고, 연산 후의 상태가 출력 $Y_i$ 입니다. 로봇이 폭발하면 출력은 없습니다.

로봇은 빈 칸을 바꾸지 않습니다. 따라서 테이프 $i$ 의 모든 칸이 비어 있으면 로봇은 아무것도 하지 않으며, 출력도 모든 칸이 비어 있는 상태입니다.

입력 $X_i$ 와 목표 출력 $Y_i$ 가 주어졌을 때, 모든 로봇이 $p$ 번째 칸을 시작 위치로 사용해 폭발 없이 모든 연산을 마치고, 각자 출력 $Y_i$ 를 얻을 수 있는 위치 $p$ ($0 \le p < n$) 를 찾고자 합니다.

입력 $X_0, \dots, X_{m-1}$ 과 출력 $Y_0, \dots, Y_{m-1}$ 의 조합 중, 그러한 위치 $p$ 가 적어도 하나 존재하는 조합의 개수를 구하세요. 답은 $10^9 + 7$ 로 나눈 나머지를 출력합니다. 두 조합이 다르다는 것은 어떤 로봇의 입력이나 출력이 다르다는 뜻입니다.

첫째 줄에 각 테이프의 칸 수 $n$ 과 테이프의 개수 $m$ 이 주어집니다. 이어지는 $m$ 개의 줄에는 로봇 $i$ 의 연산열 $S_i$ 가 R, 0, 1, * 문자로 이루어진 문자열로 주어집니다.

답을 $10^9 + 7$ 로 나눈 나머지를 정수 하나로 출력합니다.

모든 테스트 케이스에 대해 $1 \le n \le 32$, $1 \le m \le 1000$, $1 \le |S_i| \le 100$ 입니다.