Day 161-Q3 — 2026-09-26 — 挿入 DP（連結成分 DP）でジグザグ順列を数える — 端点固定つき（CEOI 2016「Kangaroo」）

📋 コピーimport sys

MOD = 10**9 + 7


def solve(n, cs, cf):
    # dp[j] = 1..i を置き終えたとき、塊（まだつながっていない連結成分）が j 個ある並べ方の数
    dp = [0] * (n + 2)
    dp[0] = 1
    for i in range(1, n + 1):
        nd = [0] * (n + 2)
        if i == cs or i == cf:
            # 端に固定された数: 端に新しい塊を作る / 端の塊の外側にくっつく
            for j in range(1, i + 1):
                nd[j] = (dp[j - 1] + dp[j]) % MOD
        else:
            fixed = (i > cs) + (i > cf)      # 既に置かれた端（その外側には置けない）
            for j in range(1, i + 1):
                # 新しい塊として隙間に置く（i は両隣より小さい谷になる）
                v = dp[j - 1] * (j - fixed) if j > fixed else 0
                # 2 つの塊の間に置いて 1 つにつなぐ（i は両隣より大きい山になる）
                v += dp[j + 1] * j
                nd[j] = v % MOD
        dp = nd
    return dp[1]


def main():
    n, cs, cf = map(int, sys.stdin.read().split())
    print(solve(n, cs, cf))


main()