まず、数列が素晴らしいかを判定する貪欲法を設計しましょう。\(N\) 個の列 \(S_1, S_2, \ldots, S_N\) を用意し、それぞれ末尾から構築します。\(A_{NK}\) から \(A_1\) までの各要素を、付け足すことのできる最も長い列に付け足していきます。もし、途中でどの部分列にも付け足せない要素があれば、構築は不可能です。そのようなことがなければ、求められる分割に成功したことになります。

もし数列を問題文が求めるように分割することができるなら、上記の貪欲法も分割を正しく行うことを示しましょう。再び要素を末尾から処理していき、「正しい」分割に則って割り当てていきます。明らかに、要素 \(X\) を部分列 \(S_i\) に割り当てられることの必要十分条件は、その時点で \(X \le K - |S_i|\) であることです。要素 \(A_i\) が部分列 \(S_X\) に割り当てられたものの、\(|S_x|<|S_y|\le K-A_i\) であるような部分列 \(S_y\)（そのようなもののうち \(|S_y|\) が最大のものを選びます）が存在したような最後の瞬間を考えます。

その \(S_y\) に次に割り当てられた要素を \(A_j\) (\(j < i\)) とします。「最後の瞬間」を考えているため、明らかに、\(A_{j+1}\) から \(A_{i-1}\) までのどの要素も \(S_x\) に割り当ててはいません。すると、\(A_i\) を \(S_y\) に割り当て、\(A_j\) を \(S_x\) に割り当てることにしても問題ないということになります。実際、\(A_i \le K - |S_y|\) かつ \(A_j \le K - |S_y| < K - |S_x|\) であるため、これは可能です。

この過程が有限であることは容易にわかります。例えば、次のような証明が可能です。\(i\) 番目の要素が、割り当て可能な列のうち最長のものに割り当てられたとき \(T_i\) が \(0\)、そうでなければ \(1\) であるような \(01\) 列 \(T_{NK}T_{NK-1}\ldots T_1\) を考えます。すると、この過程でこの文字列は辞書順で常に増加するため、貪欲法の正当性が示されました。

では、次の作業を考えます。長さ \(N + 1\) の紙切れがあり、\(0\) から \(N\) までの番号が振られたマスに分割されていて、最初のマスに \(K\) 個のボールがあります。一回の操作で、マス \(N\) にないボールを一つ選んで右隣のマスに移します。ちょうど \(NK\) 回の操作で作業が完了します。

驚くべきことに、この作業における操作列と素晴らしい列は一対一対応します。これを理解するために、貪欲法の構造をもう少しよく見ましょう。

各列に対し、あと何個の要素を付け足さなければならないか (\(L_i = K - |S_i|\)) の経過を追います。はじめ、全ての \(L_i\) は \(0\) であり、これらを全て \(0\) にすることが目標です。列を \(L_i\) でソートし、一般性を失わずに \(L_1 \le L_2 \le \ldots \le L_N\) とします。すると、現在の要素を \(X\) として、貪欲法により \(X\) 以上であるような最小の \(L_i\) を選んで \(1\) 減らすことになります。

では、この過程をボールの観点から見てみましょう。\(0\) から \(N-1\) までの各 \(i\) について、現在マス \(i\) にあるボールの個数を \(cnt_i\) とします。そして、\(1\) から \(N\) までの各 \(i\) について、\(pref_i = cnt_0 + cnt_1 + \ldots + cnt_{i-1}\) とします。すると、\(pref_1 \le pref_2 \le \ldots \le pref_N\) であり、ボールをマス \(X\) からマス \(X+1\) に移した際に起こることは \(pref_{X+1}\) が \(1\) 減るだけであることが容易にわかります。明らかに、はじめ全ての \(pref_i\) は \(K\) であり、これらを全て \(0\) にすることが目標です。

すでに何かにお気づきかもしれませんが、「偶然の一致」がもう一つあります。与えられた列 \(L_1 \le L_2 \ldots \le L_Y < L_{Y+1} \le \ldots \le L_N\) から \(L_1 \le L_2 \ldots \le L_Y < L_{Y+1}-1 \le \ldots \le L_N\) に移る方法は何通りあるでしょうか。これは、付け足す要素が範囲 \([L_Y+1, L_{Y+1}]\) に入っているときのみ可能であるため、\(L_{Y+1} - L_Y\) 通りです。

そして、\(pref_1 \le pref_2 \ldots \le pref_Y < pref_{Y+1} \le \ldots \le pref_N\) から \(pref_1 \le pref_2 \ldots \le pref_Y < pref_{Y+1} - 1 \le \ldots \le pref_N\) に移る方法は何通りでしょうか。これは、マス \(Y\) にあるボールの個数と等しく、その個数は \(pref_{Y+1} - pref_Y\) です！

ここに、列 \((L_1, \ldots, L_N)\) と作業中の \((pref_1, \ldots, pref_N)\) の間の一対一対応が明確に示されました。素晴らしい列の問題を、紙切れとボールに関するものへと言い換えていきましょう。

このとき、\(f(pos, val)\) は、\(NK-pos+1\) 番目の操作でボールをマス \(X\) から \(X+1\) に移すとして、\(pref_X < val \le pref_{X+1}\) であるような操作の列の数に一致します。この問題を全ての組 \((pos, val)\) について解きます。

\(i\) 番目の操作でボールをマス \(pos\) から \(pos+1\) に移すとします。また、他のボールのうち \(j\) 番目の現在地を \(pos_j\) とします。明らかに、\(pos + pos_1 + pos_2 + \ldots + pos_{K-1} = i-1\) でなければなりません。ボールの動かし方はボールごとに独立であることに注意すると、この状況に到達する方法の数は \(\frac{(i-1)!}{pos! pos_1! pos_2! \ldots pos_{K-1}!}\) 通り、この \(i\) 番目の操作を行ってからの操作方法の数は \(\frac{(NK-i)!}{(N-pos-1)!(N-pos_1)!\ldots (N-pos_{K-1})!}\) 通りです。従って、\(pref_{pos_1} < val < pref_{pos_1 + 1}\) であるような全ての \((i, pos, pos_1, pos_2, \ldots, pos_{N-1})\) についての \(\frac{(i-1)!}{pos! pos_1! pos_2! \ldots pos_{K-1}!} \cdot \frac{(NK-i)!}{(N-pos-1)!(N-pos_1)!\ldots (N-pos_{K-1})!}\) の和を求めることになります。このためには、マス \(pos\) の左側と右側それぞれのボールの数にも注意を払う必要があります。

これは、前計算により可能です。実際、あるボールについてそのボールの上記の積への寄与は \(g_{pos} = \frac{1}{pos!(N-pos)!}\) であるため、全ての組 \((num, bound, sum)\) について、\(num\) 個のボールを最初の \(bound\) マスに配置する方法であって \(\sum_{0 \le i < bound} cnt_i = num\) かつ \(\sum_{0 \le i < bound} cnt_i\cdot i = sum\) であるような全てのものに対する \(\prod_{0 \le i < bound} g_{pos}^{cnt_i}\) の和を計算しましょう。これは容易に \(O(N^2K^2)\) 時間で行えます。

その後、可能なあらゆる組 \((pos, num_{left}, num_{right}, sum_{left}, sum_{right}\) を試し、対応する操作列の数、すなわちこのマス \(pos\) から \(pos+1\) にボールを移す状況に到達し、そこからボールを端まで移す方法の数を計算することになります。上記の前計算を行うと計算量は \(O(N^3K^4)\) となりますが定数倍が非常に小さく、与えられた制約下で余裕を持って間に合います。