luogu#P5641. 【CSGRound2】开拓者的卓识
【CSGRound2】开拓者的卓识
题目背景
(上图转载于某神仙的题目描述)
小 K 又在做白日梦了。他进入到他的幻想中,发现了一个非常有趣的序列和一个非常有趣的数。
题目描述
我们记一个序列 的 阶子段和为 ,有
$$sum_{k,l,r}=\begin{cases}\sum\limits_{i=l}^{r}a_i&,k=1\\\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}sum_{k-1,i,j}&,k\geq 2\end{cases} $$他现在站在位置 上,他每一次往右开拓一个格子就可以增加他 IOI 赛场的 rp,所以他想尽可能的多开拓格子。可是每一次他从 开拓到 需要正确的回答 。小 K 不屑于算,就把任务交给你了。
输入格式
两行。第一行 ,表示 的长度和 。
第二行 个正整数,表示 。
输出格式
一行,第 个数为 。由于答案过大,您只需要求出答案对 取模的值。
3 1
1 2 3
1 3 6
3 2
1 2 3
1 6 20
3 10
1 2 3
1 30 420
提示
样例解释 2
$sum_{2,1,2}=sum_{1,1,1}+sum_{1,1,2}+sum_{1,2,2}=1+3+2=6$
$sum_{2,1,3}=sum_{1,1,1}+sum_{1,1,2}+sum_{1,1,3}+sum_{1,2,2}+sum_{1,2,3}+sum_{1,3,3}=1+3+6+2+5+3=20$
数据范围
测试点编号 | 的范围 | 的范围 | 的范围 |
---|---|---|---|