Ủy ban Olympic Tin học Nhật Bản quyết định làm những lá cờ lấy cảm hứng từ biểu trưng JOI để quảng bá cho kỳ thi Olympic Tin học Nhật Bản (JOI) năm nay. Mỗi lá cờ phải là một “lá cờ tốt”.

Yêu cầu

Một “lá cờ tốt” là một hình chữ nhật gồm \(M\) hàng và \(N\) cột, mỗi vị trí chứa một trong ba chữ cái J, O, I, đồng thời có ít nhất một vị trí mà ba chữ cái J, O, I được sắp xếp như hình dưới đây: O ở ngay bên phải J, và I ở ngay bên dưới chính chữ J đó.

Hình dưới đây cho hai ví dụ về “lá cờ tốt”.

Hình dưới đây cho hai ví dụ về những lá cờ không phải là “lá cờ tốt”.

Hiện tại, các giá trị \(M\), \(N\) đã được xác định và một số vị trí trên lá cờ đã được ấn định chữ cái J, O hoặc I. Cho những thông tin này, hãy viết chương trình đếm số “lá cờ tốt” có thể tạo ra và in phần dư của số đó khi chia cho \(100\,000 = 10^5\).

Dữ liệu vào

Dữ liệu gồm \(1+M\) dòng:

• Dòng \(1\) chứa hai số nguyên \(M\) và \(N\), cách nhau bởi một dấu cách, biểu thị kích thước lá cờ.
• Dòng \(1+i\) (\(1 \le i \le M\)) chứa một xâu gồm \(N\) ký tự. Mỗi ký tự là J, O, I hoặc ?. Nếu ký tự thứ \(j\) (\(1 \le j \le N\)) là J, O hoặc I, vị trí ở hàng \(i\), cột \(j\) đã được ấn định chữ cái tương ứng. Nếu ký tự đó là ?, chữ cái ở vị trí này chưa được xác định.

Dữ liệu ra

In ra một dòng chứa phần dư của số “lá cờ tốt” có thể tạo ra khi chia cho \(100\,000 = 10^5\).

Ràng buộc

• \(2 \le M \le 20\).
• \(2 \le N \le 20\).
• Mỗi xâu mô tả một hàng có đúng \(N\) ký tự, chỉ gồm J, O, I, ?.

Ví dụ

2 3
??O
IIJ

4

2 2
??
??

3

3 3
??I
???
O?J

53

5 4
JOI?
????
????
????
?JOI

28218