不要引入斯特林数，$N^2$ 的斯特林数本质就是个简单递推，只会占用大脑的空间（所以我将数据范围开到 $10^5$ 了）。

考虑容斥。

首先，设 $F_n$ 为球不同，盒不同，可空的数量。

则显然有

容斥一下，钦定有 $k$ 个盒子是空的，则本题答案为

预处理阶乘及其逆元，复杂度 $\Theta(n)$。