#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#define FI first
#define SE second
#define PB push_back
#define MT make_tuple
using namespace std;
typedef tuple<int, int> TI1;
typedef tuple<int, int, int> TI2;
static const int INF = 1ll << 24;
static const int MBIT = 1048576;
static const int mod = 100000;
static const int dx[] = { 1, -1, 0, 0, };
static const int dy[] = { 0, 0, 1, -1 };

short N, M;
short fld[21 * 21];
int dp[2][3][MBIT];
vector<int> BIT;
int ans = 0;
int all = 1;
int main() {
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            char c;
            cin >> c;
            if (c == '?') fld[i*M + j] = 3, all *= 3;
            if (c == 'J')fld[i*M + j] = 0;
            if (c == 'O')fld[i*M + j] = 1;
            if (c == 'I')fld[i*M + j] = 2;
            all %= mod;
        }
    }
    if (fld[0] != 3)dp[0][fld[0]][0] = 1;
    else {
        dp[0][0][0] = 1;
        dp[0][1][0] = 1;
        dp[0][2][0] = 1;
    }
    int maxbit = 0;
    for (int i = 0; i < M; ++i) {
        maxbit += pow(2, i);
    }
    for(int i = 0; i <= maxbit; i++){
        bool isbit=false;
        for(int j = 0 ;j < M-1; ++j){
            int bit1 = 1<<j,bit2 = 1<<(j+1);
            //cout<<bit<<endl;
            if((i&bit1)&&(i&bit2)){
                isbit=true;
                break;
            }
        }
        if(!isbit)BIT.PB(i);
    }
    int bit = 1 << M;
    int bit1 = 1 << (M - 1);
    int bit2 = 1 << (M - 2);
    for (int i = 0; i < M * N - 1; ++i) {
        int p1 = (i + 1) & 1;
        int p2 = i & 1;
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < BIT.size(); ++k) {
                int tk = BIT[k];
                int t1 = tk << 1;
                if (t1&bit)t1 -= bit;
                int t2 = t1 + 1;
                if ((tk&bit1) && j == 2 && (i + 1) % M != 0)continue;
                if (fld[i + 1] == 3) {
                    dp[p1][0][t1] = (dp[p1][0][t1] + dp[p2][j][tk]) % mod;
                    if (!(tk&bit2) || (i + 2) % M == 0)dp[p1][2][t1] = (dp[p1][2][t1] + dp[p2][j][tk]) % mod;
                    if (j == 0 && (i + 1) % M != 0)dp[p1][1][t2] = (dp[p1][1][t2] + dp[p2][j][tk]) % mod;
                    else dp[p1][1][t1] = (dp[p1][1][t1] + dp[p2][j][tk]) % mod;
                }
                else if (fld[i + 1] == 0) {
                    dp[p1][0][t1] = (dp[p1][0][t1] + dp[p2][j][tk]) % mod;
                }
                else if (fld[i + 1] == 1) {
                    if (j == 0 && (i + 1) % M != 0)dp[p1][1][t2] = (dp[p1][1][t2] + dp[p2][j][tk]) % mod;
                    else dp[p1][1][t1] = (dp[p1][1][t1] + dp[p2][j][tk]) % mod;
                }
                else if (fld[i + 1] == 2) {
                    if (!(tk&bit2) || (i + 2) % M == 0)dp[p1][2][t1] = (dp[p1][2][t1] + dp[p2][j][tk]) % mod;
                }
                dp[p2][j][tk] = 0;
            }
        }
    }
    for (int j = 0; j < 3; ++j) {
        for (int k = 0; k < BIT.size(); ++k) {
            ans += dp[(M  * N - 1) & 1][j][BIT[k]];
            ans %= mod;
        }
    }
    cout << (all%mod - ans%mod + mod) % mod << endl;
    return 0;
}

Measured memory_bytes: 6652