/* ID: espr1t TASK: KEYWORDS: */ #include #include #include using namespace std; FILE *in; FILE *out; const int MAX = 12; const int MASK = (1 << MAX); const int MOD = 1000000007; int n, m; int a[MAX][MAX]; int dyn[MAX][MAX][MASK]; int shiftAndSet(int mask, int bit) { return ((mask << 1) & ((1 << m) - 1)) | bit; } int recurse(int row, int col, int mask) { if (row >= n) return 1; if (col >= m) return recurse(row + 1, 0, mask); if (dyn[row][col][mask] != -1) return dyn[row][col][mask]; int ans = 0; // Leave white ans += recurse(row, col + 1, shiftAndSet(mask, 0)); if (ans >= MOD) ans -= MOD; // Make red bool canBeRed = a[row][col]; if (col > 0 && (mask & 1)) canBeRed = false; if (mask & (1 << (m - 1))) canBeRed = false; if (canBeRed) { ans += recurse(row, col + 1, shiftAndSet(mask, 1)); if (ans >= MOD) ans -= MOD; } return dyn[row][col][mask] = ans; } int main(void) { in = stdin; out = stdout; in = fopen("art.in", "rt"); out = fopen("art.out", "wt"); fscanf(in, "%d %d", &n, &m); for (int i = 0; i < n; i++) for (int c = 0; c < m; c++) fscanf(in, "%d", &a[i][c]); memset(dyn, -1, sizeof(dyn)); fprintf(out, "%d\n", recurse(0, 0, 0)); return 0; }