概要
割と素直な解法だと思いますが、少し公式解説と違うのかな？大差での Fastest AC にもなったので、書いておきます。
解法
$p = 90001$ とします。$K = 60$ とします。$\mathbb{F}_{p}^{\times}$ において、$1$ の原始 $60$ 乗根が存在します。これをひとつとり、 $\zeta$ とします。
ボールいくつでも許容する人を 1 人用意する代わりに「配られないボール」がない問題に帰着します。人数が $M+1$ 人になりますが、これを改めて $M$ と書きます。
人 $i$ が許容する個数の集合を $A_i$ とし、$f_i(x) = \sum_{n\in A_i} \frac{1}{n!}x^n$ とします。答は $$[x^N]N! \prod_{1\leq i\leq M}f_i(x)$$
となります。$\prod_{1\leq i\leq M}f_i(x)$ をいい感じに計算できればよさそうです。
$f_i(x)$ は、$\exp(\zeta^k x)$ （$0\leq k < K$）の線形結合として表すことができます。（なおこれは群 $\mathbb{Z}/K\mathbb{Z}$ 上の関数を、指標の線形結合で表すという表現論の基本的な結果で、$\mathbb{Z}/K\mathbb{Z}$ 上の Fourier 変換と呼べるものです。）その線形結合の係数は適当な連立 $1$ 次方程式の解として、$O(K^3)$ 時間で計算できます。（指標の直交性を利用して $O(K^2)$ 時間で求めることもできます）。
結局、各 $i$ に対して $f_i(x) = \sum_j c_{ij} \exp(a_{ij} x)$ と、高々 $60$ 項の線形結合として書けます。この形の形式的べき級数を $M$ 個かける必要がありますが、指数法則を使って状態数（指数） $p$ の dp をすれば、$O(MP)$ 時間で $\prod_i f_i(x) = \sum_{k=0}^{p-1} c_k\exp(kx)$ の形の表示が得られます。
$N![x^N]\exp(kx) = k^N$ なので、答は $c_k k^N$ のように書けます。$N$ を $p-1$ で割った余りに置き換えておけば、これは $O(P\log P)$ 時間や $O(P)$ 時間で計算できます。
