「EZEC-4.5」子序列
题目背景
作为唯一一道有背景的题，此题由出题人基于 @[Ecrade_](https://www.luogu.com.cn/user/322075) 的原创题“子集”拓展而来。
“子集”便是本题中 $k=n-1$ 的情况。
题目描述
给定一个有 $n$ 个元素的序列 $a$。
定义一个有 $x$ 个元素的序列 $s$ 的值为：
$$\sum \limits _{i=1} ^ x s_i \times \prod \limits _{i=1} ^ x s_i $$
将序列 $a$ 的一个有 $x$ 个元素的子序列表示为 $s = \{a_{p_1},a_{p_2},...,a_{p_x}\}$，其中 $p$ 为严格单调递增的序列，$1 \le p_1 \le p_x \le n$ 。
给定整数 $k$，定义序列 $a$ 的一个有 $x$ 个元素的合法的子序列 $s$ 需满足 $p_x - p_1 \le k$。
求序列 $a$ 的所有合法子序列的值之和对 $mod$ 取模的值。
输入输出格式
输入格式
第一行三个整数，$n,k,mod$ 。
第二行 $n$ 个整数，$a_i$。
输出格式
一行一个整数表示答案对 $mod$ 取模的值。
输入输出样例
输入样例 #1
4 1 1000000007
1 2 3 4输出样例 #1
150输入样例 #2
3 2 114
2 3 4输出样例 #2
65输入样例 #3
12 8 10042020
1 1 4 5 1 4 1 9 1 9 8 10输出样例 #3
2797740说明
[大样例](https://www.luogu.com.cn/paste/5sg4ahwn)
### 【样例解释】：
样例1：
- 所有合法的子序列为 $\{1\}，\{2\}，\{3\}，\{4\}，\{1,2\}，\{2,3\}，\{3,4\}$
- 答案为 $1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 4 + (1+2) \times 1 \times 2 + (2+3) \times 2 \times 3 + (3+4) \times 3 \times 4 = 150$
样例2：
- 所有合法的子序列为 $\{2\},\{3\},\{4\},\{2,3\},\{3,4\},\{2,4\},\{2,3,4\}$， 答案为 $ 407 \mod 114 = 65 $。
### 【数据范围】：
| 数据点编号 | $ n\le$ | 特殊性质 |
| :----------: | :----------: | :----------: |
|$1\sim 4$ |$20$ |无 |
|$5\sim 11$ |$10^3$ |无|
|$12$ |$10^6$ |$k=0$ |
|$13\sim 14$ |$10^5$ |$a_i=1$|
|$15\sim 17$ |$10^5$ |$mod=10^9+7$|
|$18\sim 22$ |$10^5$ |无|
|$23\sim 25$ |$10^6$ |无 |
- 对于 $100\%$ 的数据，$0 \le k < n \le 10^6 , 1 \le a_i \le 10^9 , 1 \le mod \le 10^9+7$