包除原理を用います。\(\lbrace 1,2,\dots,N-1 \rbrace\) の部分集合 \(S=\lbrace s_1,s_2,\dots,s_k \rbrace\) が与えられたときに、以下を満たす \(p\) の個数を数え上げます。

• \(i \in S\) を満たす \(i\) について、\(\max(p_1,p_2,\dots,p_i) = p_i\)

この条件は、\(s_i < j \le s_{i+1}\) を満たす \(j\) について \(s_i < p_j \le s_{i+1}\) と言い換えられます。(ただし \(s_0 = 0,s_{k+1}=N\) とします。) そして、この条件を満たす \(p\) の個数は \(\prod_{i=0}^{k} (s_{i+1}-s_i)!\) です。よって、この問題は以下のように言い換えられます。

総和が $N$ の正整数列 $a=(a_1,a_2,\dots,a_k)$ 全てについて、$(-1)^k \prod_{i=1}^{k} a_i!$ の総和を取れ。

\(a_i\) に対応する母関数は \(f(x) := \sum_{i=1}^{\infty} -i!x^i\) です。これを好きな個数並べていいので、\(f(x)^0 + f(x)^1 + f(x)^2 + ... = \frac{1}{1-f(x)}\) が答えの母関数となります。

よって FPS 逆元を用いて \(N\) 次まで \(\frac{1}{1-f(x)}\) を計算すればよいです。計算量は \(\mathrm{O}(N \log N)\) です。