\(k\) を固定する. \(k = i+ j\)となる (\(i,j\)) の組は同じ色で塗るのが必要. 逆に十分であることもよい.
例えば,以下の様にグリッドを類別する. 0から8まで移動するとき, パスによらず 0から8のマスをそれぞれ一度ずつ通る.
0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
左上と右下のマスが塗られていない場合に注意.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll h,w; cin >> h >> w;
cinv(s);
mint ans = 1;
rep(k,h-1+w-1+1){
ll x = 0;
rep(i,h) {
ll j = k-i;
if(!in(j,w)) continue;
if(s[i][j] == 'R') x |= 1;
if(s[i][j] == 'B') x |= 2;
}
ll c = pcntll(x);
if(c == 2) {
cout << 0 << endl;
return 0;
}
ans *= mint(2).pow(1-c);
}
cout << ans.val() << endl;
return 0;
}