公式解説の方針で立式すると，第二種スターリング数 (特にK個のグループに分ける方法)とベル数の母関数を組み合わせて畳み込めば計算可能なことがわかりますので，\(\mathrm{O}(N log N)\)で答えが求まります (maspy さんのアイディア)

• K個に分ける方法：\(\sum_{n \geq 0} a_n x^n/ n! = (\exp(x)-1)^K/K!\)
• ベル数 : \(\sum_{n \geq 0} b_n x^n/ n! = \exp(\exp(x)-1)\)

実装例 https://atcoder.jp/contests/arc138/submissions/30821632