module main; // https://kmjp.hatenablog.jp/entry/2015/06/12/0930 より // 動的計画法 import std; struct ModInt(long MOD) { private: long val; public: // コンストラクタ // useMod:MODで剰余を取る処理を行うかどうか this(long x, bool useMod = true) { if (useMod) { val = x % MOD; if (val < 0) val += MOD; } else val = x; } @property long value() const { return val; } @property ModInt value(long x) { val = x % MOD; if (val < 0) val += MOD; return this; } // 代入演算子 ModInt opAssign(T)(T x) if (isIntegral!T) { val = x % MOD; if (val < 0) val += MOD; return this; } // 演算代入演算子 ModInt opOpAssign(string op, T)(T rhs) pure nothrow if (is(T : ModInt) && (op == "+" || op == "-" || op == "*" || op == "/")) { static if (op == "+") { val = (val + rhs.val) % MOD; } else static if (op == "-") { val = (val - rhs.val) % MOD; } else static if (op == "*") { val = val * rhs.val % MOD; } else static if (op == "/") { val = val * rhs.inv().val % MOD; } if (val < 0) val += MOD; return this; } ModInt opOpAssign(string op, T)(T rhs) pure nothrow if (isIntegral!T && (op == "+" || op == "-" || op == "*" || op == "/")) { mixin("return this " ~ op ~ "= ModInt(rhs);"); } // 二項演算子 ModInt opBinary(string op, T)(T rhs) pure nothrow if (is(T : ModInt) && (op == "+" || op == "-" || op == "*" || op == "/")) { auto r = this; return r.opOpAssign!op(rhs); } ModInt opBinary(string op, T)(T rhs) pure nothrow if (isIntegral!T && (op == "+" || op == "-" || op == "*" || op == "/")) { auto r = this; return r.opOpAssign!op(rhs); } ModInt opBinaryRight(string op, T)(T lhs) pure nothrow if (isIntegral!T && (op == "+" || op == "-" || op == "*" || op == "/")) { ModInt r = lhs; return r.opOpAssign!op(this); } // 単項演算子 ModInt opUnary(string op)() pure nothrow if (op == "++" || op == "--") { static if (op == "++") { ++val; if (val == MOD) val = 0; } else static if (op == "--") { if (val == 0) val = MOD; --val; } return this; } ModInt opUnary(string op)() pure const nothrow if (op == "-") { if (val == 0) return ModInt(0, false); else return ModInt(MOD - val, false); } // 等号演算子 bool opEquals(ref const ModInt rhs) @safe pure const nothrow { return val == rhs.val; } bool opEquals(T)(const T rhs) @safe pure const nothrow if (isIntegral!T) { return val == rhs; } // キャスト演算子 T opCast(T : bool)() @safe pure const nothrow { return val != 0; } // 累乗 ModInt pow(T)(T n) pure const if (isIntegral!T) { ModInt x = n >= 0 ? this : inv(), r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } // MODに関する逆元 ModInt inv() pure const { long a = val, b = MOD, u = 1, v = 0; while (b) { long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return ModInt(u); } string toString() pure nothrow const { return val.to!string; } // 連想配列のためのハッシュ hash_t toHash() const @safe pure nothrow { // MMIX by Donald Knuth return cast(hash_t)(6_364_136_223_846_793_005L * val + 1_442_695_040_888_963_407L); } } immutable MOD = 1_000_000_007L; alias Mint = ModInt!MOD; int H, W; string[] S; Mint calc() { auto dp = new Mint[][](W + 1, 2); dp[0][0] = 1; foreach (x; 0 .. W) { foreach (i; 0 .. 2) { foreach (j; 0 .. 2) { bool ng = false; foreach (y; 0 .. H) if (S[y][x] != '?' && S[y][x] != '0' + (i + j + y) % 2) { ng = true; break; } if (!ng) dp[x + 1][(i + j) % 2] += dp[x][i]; } } } return dp[W][0] + dp[W][1]; } void main() { // 入力 readln.chomp.formattedRead("%d %d", H, W); S = new string[](H); foreach (ref s; S) s = readln.chomp; // 答えの計算 // 市松模様の数だけ引き算する int ok1 = 1, ok2 = 1; foreach (y; 0 .. H) foreach (x; 0 .. W) if (S[y][x] != '?') { if (S[y][x] - '0' != (y + x) % 2) ok1 = 0; if (S[y][x] - '0' == (y + x) % 2) ok2 = 0; } Mint ans = calc() - ok1 - ok2; // S を90度回転させる auto T = new string[](W); foreach (x; 0 .. W) foreach (y; 0 .. H) T[x] ~= S[y][x]; swap(S, T); swap(H, W); ans += calc(); // 答えの出力 writeln(ans); }