Problem: We have an H \times W grid, where each square is painted white or black in the initial state. Given are strings A_1, A_2, ..., A_H representing the colors of the squares in the initial state. For each pair (i, j) (1 \leq i \leq H, 1 \leq j \leq W), if the j-th character of A_i is `.`, the square at the i-th row and j-th column is painted white; if that character is `#`, that square is painted black.

Among the 2^{HW} ways for each square in the grid to be painted white or black, how many can be obtained from the initial state by performing the operations below any number of times (possibly zero) in any order? Find this count modulo 998,244,353.

* Choose one row, then paint all the squares in that row white.
* Choose one row, then paint all the squares in that row black.
* Choose one column, then paint all the squares in that column white.
* Choose one column, then paint all the squares in that column black.

Constraints

* 1 \leq H, W \leq 10
* |A_i| = W (1 \leq i \leq H)
* All strings A_i consist of `.` and `#`.
* H and W are integers.

Input

Input is given from Standard Input in the following format:


H W
A_1
A_2
\vdots
A_H


Output

Print the answer.

Examples

Input

2 2
#.
.#


Output

15


Input

2 2
.
.#


Output

15


Input

3 3
...
...
...


Output

230


Input

2 4
...
...#


Output

150


Input

6 7
.......
.......
.#.....
..#....
.#.#...
.......


Output

203949910

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

char grid[15][15];

int A[15][15];
int B[15][15];

long long MOD = 998244353;

long long memoRow[15][15][6];
long long memoCol[15][15][6];
long long ncr[15][15];
long long invNcr[15][15];

long long fact[15];
long long invFact[15];

long long pow2[15];
long long invPow2[15];

int H, W;

long long modpow(long long a, long long b){
    if(b == 0){
        return 1%MOD;
    }else if(b == 1){
        return a%MOD;
    }else{
        long long temp = modpow(a, b>>1);
        if(b&1){
            return (temp*temp%MOD) * a % MOD;
        }else{
            return temp*temp%MOD;
        }
    }
}

long long row[15][15][3];
long long col[15][15][3];

int main(){
    scanf("%d%d", &H, &W);

    for(int i = 0; i < H; i ++){
        scanf(" %s", grid[i]);
    }

    pow2[0] = 1;
    invPow2[0] = 1;
    fact[0] = 1;
    invFact[0] = 1;
    for(int i = 1; i < 14; i ++){
        pow2[i] = pow2[i-1]*2%MOD;
        fact[i] = fact[i-1]*i%MOD;
        invPow2[i] = modpow(pow2[i], MOD-2);
        invFact[i] = modpow(fact[i], MOD-2);
    }

    for(int i = 0; i < H; i ++){
        for(int j = 0; j < W; j ++){
            A[i][j] = grid[i][j] == '#';
        }
    }

    for(int i = 0; i < 14; i ++){
        ncr[i][0] = 1;
        invNcr[i][0] = 1;
        ncr[i][i] = 1;
        invNcr[i][i] = 1;
        for(int j = 1; j < i; j ++){
            ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j])%MOD;
            invNcr[i][j] = modpow(ncr[i][j], MOD-2);
        }
    }

    // Legendary Grandmaster Benq's method
    // I am trying to upsolve, but no guarantees of success in explaining :(

    /* row[i][j][d] represents number of possible patterns when i rows and j columns are unpainted
    with d distinct colors; last operation at the row coloring step

    col[i][j][d] represents number of possible patterns when i rows and j columns are unpainted
    with d distinct colors; last operation at the column coloring step
    */

    /*
    Refer to https://codeforces.com/blog/entry/73139?#comment-574602 for the order of steps/operations convention used
    */
    memset(col, 0, sizeof(col));
    memset(row, 0, sizeof(row));
    for(int j = 1; j <= W; j ++){
        // All rows are unpainted
        // There are (W choose j) = (W choose W-j) ways to choose the W-j columns painted
        // There are 2**(W-j) ways to choose the colors of the W-j painted columns
        col[H][j][2] = ncr[W][j] * pow2[W-j] % MOD;
    }

    // There are 2**W ways to paint all the columns with a specific color
    long long ans = pow2[W];

    for(int i = H; i >= 0; i --){
        for(int j = W; j >= 0; j --){
            // When d = 0, it means that we stopped the painting with exactly j columns left unpainted
            // At the previous step, either d = 1 or d = 2 (depending on the number of distinct colors painted)
            col[i][j][0] = (col[i][j][1] + col[i][j][2])%MOD;

            for(int k = 1; k < i; k ++){
                // choose l (not one, but the letter L in lowercase) out of i rows to paint
                int l = i-k;

                // i choose l ways to color the rows
                // col[i][j][2] ways to color the remaining columns if row colored
                // col[i][j][2] patterns of the remaining columns
                row[k][j][1] = (row[k][j][1] + (ncr[i][l])*(col[i][j][2]*2%MOD+col[i][j][1])%MOD) % MOD;

                // i choose l ways to color the rows
                // pow2[j]-2 ways to color the rows with 2 distinct colors
                // col[i][j][2] patterns of the remaining columns
                row[k][j][2] = (row[k][j][2] + (ncr[i][l])*((pow2[l]-2+MOD)*(col[i][j][2]) % MOD)%MOD  ) %MOD;
            }

            // col[i][j][2] ways with 2 distinct columns
            // pow2[i]-2 ways to colour the rows with two columns
            ans = (ans + col[i][j][2] * (pow2[i]-2+MOD)) % MOD;

            // row operation is actually the penultimate step, hence it has to be after the column operation
            // Remember: we are working backwards using bottom-up dp
            // Similar logic follows from the column step
            row[i][j][0] = (row[i][j][1] + row[i][j][2])%MOD;

            // similar logic for rows
            for(int k = 1; k < j; k ++){
                // choose l (not one, but the letter L in lowercase) out of j columns to paint
                int l = j-k;
                col[i][k][1] = (col[i][k][1] + (ncr[j][l])*(row[i][j][2]*2%MOD+row[i][j][1])%MOD) % MOD;
                col[i][k][2] = (col[i][k][2] + (ncr[j][l])*((pow2[l]-2+MOD)*(row[i][j][2]) % MOD)%MOD  ) %MOD;
            }

            ans = (ans + row[i][j][2] * (pow2[j]-2+MOD)) % MOD;
        }
    }

    // We then complete the summary part of the editorial
    for(int i = 0; i < (1<<H); i ++){
        for(int j = 0; j < (1<<W); j ++){
            // Check that there are two colors in every row and column that remains

            // Row check: the bits set are the ones which correspond to the rows and columns being chosen respectively
            bool valid = true;
            for(int k = 0; k < H; k ++){
                if(!(i&(1<<k))){
                    int temp = 0;
                    for(int l = 0; l < W; l ++){
                        if(!(j&(1<<l))){
                            temp |= (1<<A[k][l]);
                        }
                    }

                    if(temp != 3){
                        valid = false;
                        break;
                    }
                }
            }

            if(valid){
                // Logic is similar for columns
                for(int l = 0; l < W; l ++){
                    if(!(j&(1<<l))){
                        int temp = 0;
                        for(int k = 0; k < H; k ++){
                            if(!(i&(1<<k))){
                                temp |= (1<<A[k][l]);
                            }
                        }

                        if(temp != 3){
                            valid = false;
                            break;
                        }
                    }
                }
            }

            if(valid){
                int rowsRemaining = H-__builtin_popcount(i);
                int colsRemaining = W-__builtin_popcount(j);

                int x = rowsRemaining;
                int y = colsRemaining;

                // Two cases: last operation is row or last operation is column
                // d=0 because only then, this indicates that it is the final step and that it is not possible to remove more columns
                // This is why the row and column check for two distinct colors is necessary.
                // There are H choose x ways to permute the rows painted and W choose y ways to permute the columns painted
                // These are invalid double-counts since the set of rows and columns painted have been fixed.
                // Hence, we need to divide the number of ways by invNcr[H][x] and invNcr[W][y]
                ans = (ans + (row[x][y][0] + col[x][y][0])%MOD*invNcr[H][x]%MOD*invNcr[W][y]%MOD)%MOD;
            }
        }
    }

    printf("%lld", ans);

    return 0;
}