JOI 깃발

일본 정보올림피아드 위원회는 일본 정보올림피아드(JOI)를 홍보하기 위해서 JOI로고를 모티브로 한 깃발을 만들었다. 깃발은 "좋은 깃발" 이어야 한다. "좋은 깃발"은 알파벳 J, O, I중 하나의 문자를 M행 N열 사각형 형태로 배치한 것으로, 아래 그림과 같이 배치되어 있는 곳이 깃발에 적어도 한 곳 있는 깃발이다.

다음은 "좋은 깃발"의 예이다.

다음은 "좋은 깃발"이 아닌 예이다.

일부 위치에는 이미 그 칸을 채울 문자가 정해져 있다. 이때, M, N이 주어졌을 때, 좋은 깃발을 만들 수 있는 방법의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 깃발의 크기 M과 N이 주어진다. (2 ≤ M, N ≤ 20)

다음 M개 줄에는 깃발의 모양인 N개 문자가 주어진다. 각 문자는 J, O, I, ?중 하나이다. J, O, I인 경우에는 i행 j열 위치의 문자가 이미 그 문자로 정해져 있는 뜻이고, ?는 아직 정해져 있지 않다는 뜻이다.

첫째 줄에 "좋은 깃발"을 만들 수 있는 방법의 수를 100000으로 나눈 나머지를 출력한다.

예제 1의 경우 아래와 같이 좋은 깃발을 만들 수 있다.