public import std; DList!string scan_buffer; DList!char char_buffer; static this() { scan_buffer = DList!(string)(); char_buffer = DList!(char)(); } void cin()() { } void cin(T, A...)(ref T a, ref A tail) { import std.traits : isArray; static if (typeof(a).stringof == "string") { if (!char_buffer.empty) { a = char_buffer.array.map!(x => x.to!string).join(); char_buffer.clear(); } else { while (scan_buffer.empty) { foreach (t; readln.split) { if (t.length == 0) { continue; } scan_buffer.insert(t); } } auto token = scan_buffer.front; scan_buffer.removeFront(); a = token; } } else static if (typeof(a).stringof == "char") { if (!char_buffer.empty) { a = char_buffer.front(); char_buffer.removeFront(); } else { while (scan_buffer.empty) { foreach (t; readln.split) { if (t.length == 0) { continue; } scan_buffer.insert(t); } } auto token = scan_buffer.front; scan_buffer.removeFront(); a = token[0]; if (token.length > 1) { foreach (c; token[1 .. $]) { char_buffer.insertBack(c); } } } } else static if (typeof(a).stringof == "char[]") { if (a.length == 0) { string token; cin(token); foreach (c; token) { a ~= c; } } else { foreach (ref v; a) { cin(v); } } } else static if (isArray!(typeof(a))) { foreach (ref v; a) { cin(v); } } else static if (isTuple!(typeof(a))) { foreach (i, _; a) { cin(a[i]); } } else { if (!char_buffer.empty) { writeln(char_buffer.array.map!(x => x.to!string)); a = char_buffer.array.map!(x => x.to!string).join().to!T; char_buffer.clear(); } else { while (scan_buffer.empty) { foreach (t; readln.split) { if (t.length == 0) { continue; } scan_buffer.insert(t); } } auto token = scan_buffer.front; scan_buffer.removeFront(); a = token.to!T; } } cin(tail); } bool chmin(T)(ref T a, T b) { if (a > b) { a = b; return true; } return false; } bool chmax(T)(ref T a, T b) { if (a < b) { a = b; return true; } return false; } alias PQueue(T = long, alias less = "a> 32; immutable ulong bu = b >> 32; immutable ulong al = a & ((1UL << 32) - 1); immutable ulong bl = b & ((1UL << 32) - 1); ulong t = al * bl; immutable ulong w3 = t & ((1UL << 32) - 1); ulong k = t >> 32; t = au * bl + k; k = t & ((1UL << 32) - 1); immutable ulong w1 = t >> 32; t = al * bu + k; k = t >> 32; return [au * bu + w1 + k, t << 32 + w3]; } struct Barrett { uint _m; ulong im; this(uint m) @safe @nogc pure nothrow { _m = m; im = (cast(ulong)(-1)) / m + 1; } uint umod() @safe @nogc pure nothrow { return _m; } uint mul(uint a, uint b) @safe @nogc pure nothrow { ulong z = a; z *= b; immutable ulong x = umul128(z, im)[0]; uint v = cast(uint)(z - x * _m); if (_m <= v) v += _m; return v; } } long ctPowMod(long x, long n, int m) @safe pure nothrow @nogc { if (m == 1) return 0; uint _m = cast(uint) m; ulong r = 1; ulong y = safeMod(x, m); while (n) { if (n & 1) r = (r * y) % _m; y = (y * y) % _m; n >>= 1; } return r; } bool ctIsPrime(int n) @safe pure nothrow @nogc { if (n <= 1) return false; if (n == 2 || n == 7 || n == 61) return true; if (n % 2 == 0) return false; long d = n - 1; while (d % 2 == 0) d /= 2; foreach (a; [2, 7, 61]) { long t = d; long y = ctPowMod(a, t, n); while (t != n - 1 && y != 1 && y != n - 1) { y = y * y % n; t <<= 1; } if (y != n - 1 && t % 2 == 0) { return false; } } return true; } enum bool isPrime(int n) = ctIsPrime(n); Tuple!(long, long) invGcd(long a, long b) @safe pure nothrow @nogc { a = safeMod(a, b); if (a == 0) return Tuple!(long, long)(b, 0); long s = b, t = a, m0 = 0, m1 = 1; while (t) { immutable long u = s / t; s -= t * u; m0 -= m1 * u; long tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp; } if (m0 < 0) m0 += b / s; return Tuple!(long, long)(s, m0); } int ctPrimitiveRoot(int m) @safe pure nothrow @nogc { if (m == 2) return 1; if (m == 167_772_161) return 3; if (m == 469_762_049) return 3; if (m == 754_974_721) return 11; if (m == 998_244_353) return 3; int[20] divs; divs[0] = 2; int cnt = 1; int x = (m - 1) / 2; while (x % 2 == 0) x /= 2; for (int i = 3; (cast(long) i) * i <= x; i += 2) if (x % i == 0) { divs[cnt++] = i; while (x % i == 0) x /= i; } if (x > 1) divs[cnt++] = x; for (int g = 2;; g++) { bool ok = true; foreach (i; 0 .. cnt) if (ctPowMod(g, (m - 1) / divs[i], m) == 1) { ok = false; break; } if (ok) return g; } } enum primitiveRoot(int m) = ctPrimitiveRoot(m); struct StaticModInt(int m) if (1 <= m) { import std.traits : isSigned, isUnsigned, isSomeChar; alias mint = StaticModInt; public: static int mod() { return m; } static mint raw(int v) { mint x; x._v = v; return x; } this(T)(T v) if (isSigned!T) { long x = cast(long)(v % cast(long)(umod())); if (x < 0) x += umod(); _v = cast(uint)(x); } this(T)(T v) if (isUnsigned!T || isSomeChar!T) { _v = cast(uint)(v % umod()); } this(bool v) { _v = cast(uint)(v) % umod(); } auto opAssign(T)(T v) if (isSigned!T || isUnsigned!T || isSomeChar!T || is(T == bool)) { return this = mint(v); } inout uint val() pure { return _v; } ref mint opUnary(string op)() pure nothrow @safe if (op == "++") { _v++; if (_v == umod()) _v = 0; return this; } ref mint opUnary(string op)() pure nothrow @safe if (op == "--") { if (_v == 0) _v = umod(); _v--; return this; } mint opUnary(string op)() if (op == "+" || op == "-") { mint x; return mixin("x " ~ op ~ " this"); } ref mint opOpAssign(string op, T)(T value) if (!is(T == mint)) { mint y = value; return opOpAssign!(op)(y); } ref mint opOpAssign(string op, T)(T value) if (op == "+" && is(T == mint)) { _v += value._v; if (_v >= umod()) _v -= umod(); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "-" && is(T == mint)) { _v -= value._v; if (_v >= umod()) _v += umod(); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "*" && is(T == mint)) { ulong z = _v; z *= value._v; _v = cast(uint)(z % umod()); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "/" && is(T == mint)) { return this = this * value.inv(); } ref mint opOpAssign(string op, T)(T value) if (op == "^^" && (is(T == int) || is(T == long))) { return this = this.pow(value); } mint pow(long n) const pure { assert(0 <= n); mint x = this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } mint inv() const pure { static if (prime) { assert(_v); return pow(umod() - 2); } else { auto eg = invGcd(_v, mod()); assert(eg[0] == 1); return mint(eg[1]); } } mint opBinary(string op, R)(const R value) const pure if (op == "+" || op == "-" || op == "*" || op == "/") { static if (is(R == mint)) { mint x; x += this; return x.opOpAssign!(op)(value); } else { mint x; x += this; mint y = value; return x.opOpAssign!(op)(y); } } mint opBinary(string op, R)(const R value) const pure if (op == "^^") { return pow(value); } mint opBinaryRight(string op, L)(const L value) const if (!is(L == mint)) { mint y = value; return y.opBinary!(op)(this); } bool opEquals(R)(const R value) const { static if (is(R == mint)) { return _v == value._v; } else { mint y = mint(value); return this == y; } } private: uint _v; uint umod() pure const { return m; } enum bool prime = isPrime!(m); } struct DynamicModInt(int id) { import std.traits : isSigned, isUnsigned, isSomeChar; alias mint = DynamicModInt; public: static int mod() { return bt.umod(); } static void setMod(int m) { assert(1 <= m); bt = Barrett(m); } static mint raw(int v) { mint x; x._v = v; return x; } this(T)(T v) if (isSigned!T) { long x = cast(long)(v % cast(long)(umod())); if (x < 0) x += umod(); _v = cast(uint)(x); } this(T)(T v) if (isUnsigned!T || isSomeChar!T) { _v = cast(uint)(v % umod()); } this(bool v) { _v = cast(uint)(v) % umod(); } auto opAssign(T)(T v) if (isSigned!T || isUnsigned!T || isSomeChar!T || is(T == bool)) { return this = mint(v); } inout uint val() { return _v; } ref mint opUnary(string op)() nothrow @safe if (op == "++") { _v++; if (_v == umod()) _v = 0; return this; } ref mint opUnary(string op)() nothrow @safe if (op == "--") { if (_v == 0) _v = umod(); _v--; return this; } mint opUnary(string op)() if (op == "+" || op == "-") { mint x; return mixin("x " ~ op ~ " this"); } ref mint opOpAssign(string op, T)(T value) if (!is(T == mint)) { mint y = value; return opOpAssign!(op)(y); } ref mint opOpAssign(string op, T)(T value) if (op == "+" && is(T == mint)) { _v += value._v; if (_v >= umod()) _v -= umod(); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "-" && is(T == mint)) { _v -= value._v; if (_v >= umod()) _v += umod(); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "*" && is(T == mint)) { _v = bt.mul(_v, value._v); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "/" && is(T == mint)) { return this = this * value.inv(); } ref mint opOpAssign(string op, T)(T value) if (op == "^^" && (is(T == int) || is(T == long))) { return this = this.pow(value); } mint pow(long n) const { assert(0 <= n); mint x = this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } mint inv() const { auto eg = invGcd(_v, mod()); assert(eg[0] == 1); return mint(eg[1]); } mint opBinary(string op, R)(const R value) if (op == "+" || op == "-" || op == "*" || op == "/") { static if (is(R == mint)) { mint x; x += this; return x.opOpAssign!(op)(value); } else { mint y = value; return opOpAssign!(op)(y); } } mint opBinary(string op, R)(const R value) const if (op == "^^") { return pow(value); } mint opBinaryRight(string op, L)(const L value) const if (!is(L == mint)) { mint y = value; return y.opBinary!(op)(this); } bool opEquals(R)(const R value) const { static if (is(R == mint)) { return _v == value._v; } else { mint y = mint(value); return this == y; } } private: uint _v; static Barrett bt = Barrett(998_244_353); uint umod() { return bt.umod(); } } alias modint998244353 = StaticModInt!(998244353); alias modint1000000007 = StaticModInt!(1000000007); alias modint = DynamicModInt!(-1); alias mint = modint998244353; void main() { int W, H; cin(W, H); auto key = new int[W]; key.fill(-1); auto dsu = new Dsu(W); bool zero = false; int und = W; foreach (i; 0 .. H) { auto Q = new char[W]; cin(Q); auto ch = new int[26]; ch.fill(-1); foreach (j, c; Q) { if (c == '?') continue; if (c >= '0' && c <= '9') { int u = dsu.leader(j); if (key[u] == -1) { key[u] = c - '0'; und--; } else if (key[u] != c - '0') { zero = true; } } else { if (ch[c - 'a'] == -1) { ch[c - 'a'] = cast(int) j; } else { int u = dsu.leader(ch[c - 'a']); int v = dsu.leader(j); if (dsu.same(u, v)) { continue; } if (key[u] != -1 && key[v] != -1 && key[u] != key[v]) { zero = true; } else { int k = -1; k.chmax(key[u]); k.chmax(key[v]); if (key[u] != key[v] || key[u] == -1) { und--; } int r = dsu.merge(u, v); key[r] = k; } } } } if (zero) { 0.writeln; } else { (mint(10) ^^ und).val.writeln; } } }