随便想的题目求解

给定 $n,k$，求有多少个长度为 $n$ 的排列满足其前缀和序列中存在 $k$。$k$ 与 $n^2$ 同阶。

蒟蒻只会 $O(n^2k)=O(n^4)$ 的 DP。