#include #include using namespace std; using mint = atcoder::modint998244353; int main() { int h,w; cin >> h >> w; vector s(h); for (int i=0; i> s[i]; vector dp(h, vector(h, mint(0))); dp[0][0] = 1; // dp[i][j][k]: i列目まで決めて、Bobがその列で到達した最大の行がj、Aliceがその行で到達した最小の行がk // 遷移は累積和を用いて高速化可能、O(H^2W) for (int i=1; i(h, mint(0))); for (int j=0; j 0 && dpn[j-1][k].val() != 0) dpn[j][k] += dpn[j-1][k]; if (dp[j][k].val() != 0) dpn[j][k] += dp[j][k]; } swap(dp, dpn); } cout << dp[h-2][h-1].val() << '\n'; }