RT，题面如下：

给定一个长为 $n$ 的序列 $a_1,\cdots,a_n$（初始全为 0），$m$ 次操作，每次给定 $l,r,k$，对 $[l,r]$ 内的每个 $i$ 都令 $a_i$ 加上 $\binom{i-l+k}{k}$。最后输出整个序列，对 $10^9+7$ 取模。

$n,m \leq 5 \times 10^5$，$0 \leq k \leq 20$

容易发现加的这个东西实际上是序列 $1,1,1,\cdots$ 的 $k$ 阶前缀和的前 $r-l+1$ 项，所以考虑建立 $1$ 到 $k$ 阶的差分数组，转换为单点修改。

那么关键在于如何在高阶差分数组中将修改限制在区间内。我手推了一个 k=3 的情况：

$0,1,3,6,10,15,0,0,0 \ (\Delta^0)$

$0,1,2,3,4,5,-15,0,0 \ (\Delta^1)$

$0,1,1,1,1,1,-20,15,0 \ (\Delta^2)$

$0,1,0,0,0,0,-21,35,-15 (\Delta^3)$

然后把后面的补项列出来：

$-C_{r-l+k}^k$

$-C_{r-l+k}^k-C_{r-l+k-1}^{k-1},C_{r-l+k}^k$

$-C_{r-l+k}^k - C_{r-l+k-1}^{k-1} - C_{r-l+k-2}^{k-2},2C_{r-l+k}^k + C_{r-l+k-1}^{k-1} ,-C_{r-l+k}^k$

抽象一下，后续大概是这样：

$(-1,-1,-1,-1),(3,2,1),(-3,-1),(1)$

$(-1,-1,-1,-1,-1),(4,3,2,1),(-6,-3,-1),(4,1),(-1)$

$(-1,-1,-1,-1,-1,-1),(5,4,3,2,1),(-10,-6,-3,-1),(10,4,1),(-5,-1),(1)$

到这里我会 $O(nk^2)$ 了，请问大佬怎么砍掉一个 $k$……