intmain(){ int n, m; cin >> n >> m; for (int l = 1; l <= m; l++) { for (int r = l; r <= m; r++) { dp[l][r][1][1] = 1; } } int64 ans = 0; for (int i = 1; i <= n; i++) { int64 sum = 0; for (int l = 1; l <= m; l++) { for (int r = l; r <= m; r++) { for (int sl = 0; sl <= 1; sl++) { for (int sr = 0; sr <= 1; sr++) { sum += dp[l][r][sl][sr]; sum %= MOD; } } } } ans += sum * (n - i + 1); // 统计的是上一行的答案 ans %= MOD;
// 左侧收缩 for (int l = 1; l < m; l++) { for (int r = l + 1; r <= m; r++) { for (int sl = 0; sl <= 1; sl++) { for (int sr = 0; sr <= 1; sr++) { dp[l + 1][r][0][sr] += dp[l][r][sl][sr]; dp[l + 1][r][0][sr] %= MOD; } } } }
// 右侧收缩 for (int l = m - 1; l >= 1; l--) { for (int r = m; r >= l + 1; r--) { for (int sl = 0; sl <= 1; sl++) { for (int sr = 0; sr <= 1; sr++) { dp[l][r - 1][sl][0] += dp[l][r][sl][sr]; dp[l][r - 1][sl][0] %= MOD; } } } }
// 左侧扩张 for (int l = m; l >= 2; l--) { for (int r = m; r >= l; r--) { for (int sr = 0; sr <= 1; sr++) { dp[l - 1][r][1][sr] += dp[l][r][1][sr]; dp[l - 1][r][1][sr] %= MOD; } } }
// 右侧扩展 for (int l = 1; l < m; l++) { for (int r = l; r < m; r++) { for (int sl = 0; sl <= 1; sl++) { dp[l][r + 1][sl][1] += dp[l][r][sl][1]; dp[l][r + 1][sl][1] %= MOD; } } } } cout << ans << endl; }