#nullable enable using System.Numerics; void Run() { var h = Int(); var w = Int(); var g = new bool[h, w]; for (var i = 0; i < h; i++) { var row = String(); for (var j = 0; j < w; j++) g[i, j] = row[j] == '.'; } var rs = new int[h, w]; for (var i = 0; i < h; i++) { var ls = w; for (var j = w - 1; j >= 0; j--) { if (!g[i, j]) ls = j; rs[i, j] = ls; } } var dp = w.Repeat(() => new RangeAddPointGet(w)); dp[1].Add(0, 1, 1); var f = true; var x = 0; for (var lp = 0; lp < h * 2 - 4; lp++) { var ep = w.Repeat(() => new RangeAddPointGet(w)); for (var i = 0; i < w; i++) for (var j = 0; j < w; j++) { if (!g[x, i]) continue; var v = dp[i].Get(j); if (v == 0) continue; if (f) { if (i <= j) continue; var start = Math.Max(i, j + 1); if (start >= w) continue; var k = rs[x, start]; ep[j].Add(start, k, v); } else { if (i >= j) continue; var k = Math.Min(rs[x, i], j); ep[j].Add(i, k, v); } } dp = ep; if (f) x++; f = !f; } ModInt ans = 0; for (var i = 0; i < w; i++) for (var j = 0; j < w; j++) if(g[h - 2, i] && g[h - 1, j]) ans += dp[i].Get(j); Out(ans); } #region AtCoderIO _io_; var _backend_ = new StandardIOBackend(); _io_ = new(){ Backend = _backend_ }; Run(); _backend_.Flush(); string String() => _io_.Next(); int Int() => int.Parse(String()); void Out(object? x, string? sep = null) => _io_.Out(x, sep); class AtCoderIO { public required StandardIOBackend Backend { get; init; } Memory _input = Array.Empty(); int _iter = 0; public string Next() { while (_iter >= _input.Length) (_input, _iter) = (Backend.ReadLine().Split(' '), 0); return _input.Span[_iter++]; } public void Out(object? x, string? separator = null) { if (x == null) return; separator ??= Environment.NewLine; if (x is System.Collections.IEnumerable a and not string) { var objects = a.Cast(); if (separator == Environment.NewLine && !objects.Any()) return; x = string.Join(separator, objects); } Backend.WriteLine(x); } } class StandardIOBackend { readonly StreamReader _sr = new(Console.OpenStandardInput()); readonly StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false }; public string ReadLine() => _sr.ReadLine()!; public void WriteLine(object? value) => _sw.WriteLine(value); public void Flush() => _sw.Flush(); } #endregion static class Extensions { public static T[] Repeat(this int time, Func F) => Enumerable.Range(0, time).Select(_ => F()).ToArray(); } interface IAdditiveGroup : IAdditiveIdentity, IAdditionOperators, ISubtractionOperators where T : IAdditiveGroup { T AdditiveInverse(); } interface IMultiplicativeGroup : IMultiplicativeIdentity, IMultiplyOperators, IDivisionOperators where T : IMultiplicativeGroup { T MultiplicativeInverse(); } readonly record struct ModInt : IEqualityOperators, IAdditiveGroup, IMultiplicativeGroup { public const int Mod = 998244353; int V { get; init; } public ModInt(long value) { var v = value % Mod; if (v < 0) v += Mod; V = (int)v; } static ModInt New(int value) => new(){ V = value }; public static implicit operator ModInt(long v) => new(v); public static implicit operator int(ModInt modInt) => modInt.V; public static ModInt AdditiveIdentity => New(0); public static ModInt operator +(ModInt a, ModInt b) { var v = a.V + b.V; if (v >= Mod) v -= Mod; return New(v); } public ModInt AdditiveInverse() { if (V == 0) return AdditiveIdentity; return New(Mod - V); } public static ModInt operator -(ModInt a, ModInt b) { var v = a.V - b.V; if (v < 0) v += Mod; return New(v); } public static ModInt MultiplicativeIdentity => New(1); public static ModInt operator *(ModInt a, ModInt b) => New((int)((long)a.V * b.V % Mod)); public ModInt MultiplicativeInverse() { if (V == 0) throw new DivideByZeroException(); var (d, x, _) = ExtendedGCD(V, Mod); if (d > 1) throw new DivideByZeroException(); return x; } public static ModInt operator /(ModInt a, ModInt b) => a * b.MultiplicativeInverse(); static long Power(long v, ulong p, long mod) { var (res, k) = (1L, v); while (p > 0) { if ((p & 1) > 0) res = res * k % mod; k = k * k % mod; p >>= 1; } return res; } public ModInt Power(long p) => p < 0 ? (MultiplicativeIdentity / V).Power(-p) : Power(V, (ulong)p, Mod); static (long d, long x, long y) ExtendedGCD(long a, long b) { var (x0, y0, x1, y1) = (1L, 0L, 0L, 1L); while (b != 0) { var q = a / b; (a, b) = (b, a - q * b); (x0, y0, x1, y1) = (x1, y1, x0 - q * x1, y0 - q * y1); } return (a, x0, y0); } public override string ToString() => V.ToString(); } class FenwickTree where T : IAdditiveGroup { public FenwickTree(int length) { _values = new T[length + 2]; } public void Add(int i, T value) { var values = _values.Span; while (i < values.Length) { values[i] += value; i += i & -i; } } public T Sum(int i) { var values = _values.Span; var res = T.AdditiveIdentity; while (i > 0) { res += values[i]; i -= i & -i; } return res; } readonly Memory _values; } // [0..N) class RangeAddPointGet where T : IAdditiveGroup { public RangeAddPointGet(int length) { _data = new FenwickTree(length); } public void Add(int l, int r, T value) // [l, r) { _data.Add(l + 1, value); _data.Add(r + 1, T.AdditiveIdentity - value); } public T Get(int at) => _data.Sum(at + 1); readonly FenwickTree _data; }