题目背景

作为唯一一道有背景的题，此题由出题人基于

“子集”便是本题中 $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$ 取模的值。

4 1 1000000007
1 2 3 4

150

3 2 114
2 3 4

65

12 8 10042020
1 1 4 5 1 4 1 9 1 9 8 10

2797740

提示

大样例

【样例解释】：

样例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$		$mod=10^9+7$
$18\sim 22$		无
$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$