// Enjoy your stay. Code by evima on 2021/02/05 #include #define LOOPVAR_TYPE long #define all(x) (x).begin(), (x).end() #define sz(x) ((LOOPVAR_TYPE)(x).size()) #define foreach(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++) #define GET_MACRO(_1, _2, _3, NAME, ...) NAME #define _rep(i, n) _rep2(i, 0, n) #define _rep2(i, a, b) for(LOOPVAR_TYPE i = (LOOPVAR_TYPE)(a); i < (LOOPVAR_TYPE)(b); i++) #define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__) template bool tomin(T &a, const T &b) { return (b < a) ? (a = b, true) : false; } template bool tomax(T &a, const T &b) { return (a < b) ? (a = b, true) : false; } #define fir first #define sec second #define mp make_pair #define mt make_tuple #define pb push_back #define eb emplace_back const double EPS = 1e-9; const double PI = 3.141592653589793238462; const long INF = 1070000000LL; const long MOD = 998244353LL; using namespace std; const int MR = 100, MC = 10, MN = 100; const int B = MC / 2 + 2; int R, C, N; char ch[MR][MC + 1]; vector int2baseB(int n){ vector ret; rep(i, C + 1){ ret.eb(n % B); n /= B; } return ret; } int baseB2int(vector v){ int ret = 0; for(int i = C; i >= 0; --i){ ret = ret * B + v[i]; } return ret; } void normalize(vector& v){ int to[B + 1] = {}, num = 1; for(int& x: v){ if(x){ if(!to[x]){ to[x] = num++; } x = to[x]; } } } unordered_map memo[MR + 1][MC + 1][MN + 1][2]; long f(int y, int x, int n, int flag, int state){ if(n > N) return 0; auto it = memo[y][x][n][flag].find(state); if(it != memo[y][x][n][flag].end()){ return it->sec; } long& ret = memo[y][x][n][flag][state]; auto v = int2baseB(state); vector cnt(B); for(int x: v) ++cnt[x]; if(y == R){ if(all_of(all(v), [](int x){ return x <= 1; })){ int m = n + !!v[C]; rep(i, C){ m += !!v[i] ^ !!v[i + 1]; } ret = m == N; } }else if(x == C){ vector nv(C + 1); copy(v.begin(), v.end() - 1, nv.begin() + 1); normalize(nv); ret = f(y + 1, 0, n + (!!v[C - 1] ^ !!v[C]), flag, baseB2int(nv)); }else{ // ab // c! int a = v[x], b = v[x + 1], c = x ? v[x - 1] : 0; int s = !!a + !!b + !!c; if(ch[y][x] != '#' && !(!a && b && c || b && cnt[b] == 1 && cnt[0] != C || a && b && cnt[b] == 2 && cnt[0] != C - 1)){ // . auto nv = v; nv[x] = 0; normalize(nv); ret += f(y, x + 1, n + s % 2, flag || b && cnt[b] == 1 || a && b && cnt[b] == 2, baseB2int(nv)); } if(ch[y][x] != '.' && !flag && (!(a && !b && !c || !a && b && (b == c)))){ // # auto nv = v; if(!b && !c){ nv[x] = B; }else if(b && c){ nv[x] = b; rep(i, C + 1){ if(nv[i] == c){ nv[i] = b; } } }else if(b){ nv[x] = b; }else{ // c nv[x] = c; } normalize(nv); ret += f(y, x + 1, n + (s + 1) % 2, flag, baseB2int(nv)); } } return ret %= MOD; } int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> R >> C >> N; cout << f(0, 0, 0, 0, 0) << endl; }