#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include #include #include #include using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i void chmin(A& l, const A& r){ if(r < l) l = r; } template void chmax(A& l, const A& r){ if(l < r) l = r; } using namespace std; #include #include namespace nachia{ // ax + by = gcd(a,b) // return ( x, - ) std::pair ExtGcd(long long a, long long b){ long long x = 1, y = 0; while(b){ long long u = a / b; std::swap(a-=b*u, b); std::swap(x-=y*u, y); } return std::make_pair(x, a); } } // namespace nachia namespace nachia{ template struct StaticModint{ private: using u64 = unsigned long long; unsigned int x; public: using my_type = StaticModint; template< class Elem > static Elem safe_mod(Elem x){ if(x < 0){ if(0 <= x+MOD) return x + MOD; return MOD - ((-(x+MOD)-1) % MOD + 1); } return x % MOD; } StaticModint() : x(0){} StaticModint(const my_type& a) : x(a.x){} StaticModint& operator=(const my_type&) = default; template< class Elem > StaticModint(Elem v) : x(safe_mod(v)){} unsigned int operator*() const { return x; } my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator+(const my_type& r) const { my_type res = *this; return res += r; } my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; } my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; } my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; } my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; } bool operator==(const my_type& r) const { return x == r.x; } my_type pow(unsigned long long i) const { my_type a = *this, res = 1; while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; } return res; } my_type inv() const { return my_type(ExtGcd(x, MOD).first); } unsigned int val() const { return x; } int hval() const { return int(x > MOD/2 ? x - MOD : x); } static constexpr unsigned int mod() { return MOD; } static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; } my_type& operator/=(const my_type& r){ return operator*=(r.inv()); } my_type operator/(const my_type& r) const { return operator*(r.inv()); } }; } // namespace nachia using Modint = nachia::StaticModint<998244353>; void testcase(){ i64 H, W; cin >> H >> W; vector A(H+1); rep(i,H) cin >> A[i]; rep(i,H) A[i].push_back('#'); A[H] = string(W+1, '#'); vector> dp(1, vector(1,1)); for(i64 i=1; i> nx(p+1, vector(p+1,0)); rep(a,p) rep(b,p) if(a<=b){ nx[a][b] += dp[a][b]; nx[a+1][b] += dp[a][b]; nx[a][b+1] += dp[a][b]; nx[a+1][b+1] += dp[a][b]; } string ref; for(i64 x=0; x> nx2(q, vector(q,0)); rep(a,q) rep(b,q) if(a