便利のため，\(A_0=1\) とします． この問題における操作は，次のように言い換えることが可能です．

• \(A_x=1\) を満たす \(x\) (\(0 \leq x \leq N\)) を選ぶ．その後，\(X\) 座標を \(x\) 増やし，\(Y\) 座標を \(1\) 増やす． 操作後の座標 \((p,q)\) は \(q \leq p\) を満たす必要がある．

このようにすると，操作はちょうど \(N\) 回行われることになります．\(i\) 回目の操作で選ばれた \(x\) を \(B_i\) と表すことにします．

すると問題は，次の条件を満たす長さ \(N\) の非負数列 \(B_i\) を数えることに対応します．

• \(A_{B_i}=1\)
• \(B_1+B_2+\cdots+B_i \geq i\)
• \(B_1+B_2+\cdots+B_N=N\)

ここで，次の条件を満たす長さ \(N+1\) の非負数列 \(C\) を考えます．

• \(A_{C_i}=1\)
• \(C_1+C_2+\cdots+C_{N+1}=N\)

このとき，\((\) 条件を満たす \(B\) の個数 \() \times (N+1)=\) 条件を満たす \(C\) の個数となります．

これは，\((\)条件を満たす \(B, 1\) 以上 \(N+1\) 以下の整数 \(k)\) というペアと \(C\) の間に全単射が存在することから示せます．

\(\rightarrow\) の方向は，次のように作れます．

• \((0,B_1,B_2,\cdots,B_N)\) という数列を作る．その後，先頭の \(0\) が先頭から \(k\) 番目に来るようにこの数列を cyclic shift し，これを \(C\) とする．

\(\leftarrow\) の方向は，次のように作れます．

• \(C_1+C_2+\cdots+C_i-i\) の値が最小になる \(i\) を \(k\) とする．複数ある場合は最小の \(i\) をとる．その後，上と逆の手順で \(B\) を復元する．

\(C\) の個数は，\(f(x)=\sum_{0 \leq i \leq N} A_i x^i\) として，\(f^{N+1}(x)\) を計算すればわかります． これは FFT と繰り返し二乗法を使えば \(O(N \log^2N)\) 時間でできます． また，FPS pow を用いれば \(O(N \log N)\) でできます． どちらにせよ十分高速です．

解答例(C++)