Description

Given a sequence $a$ with $n$ elements.

Define the value of a sequence $s$ with $x$ elements as:

$$\sum \limits _{i=1} ^ x s_i \times \prod \limits _{i=1} ^ x s_i$$

Represent an $x$-element subsequence of $a$ as $s = \{a_{p_1}, a_{p_2}, ..., a_{p_x}\}$, where $p$ is a strictly increasing sequence and $1 \le p_1 \le p_x \le n$.

Given an integer $k$, define that an $x$-element subsequence $s$ of $a$ is legal if it satisfies $p_x - p_1 \le k$.

Compute, modulo $mod$, the sum of the values of all legal subsequences of $a$.

Input Format

The first line contains three integers, $n, k, mod$.

The second line contains $n$ integers, $a_i$.

Output Format

Output one integer, the answer modulo $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

Hint

Large sample

Sample Explanation.

Sample 1.

• All legal subsequences are $\{1\}, \{2\}, \{3\}, \{4\}, \{1,2\}, \{2,3\}, \{3,4\}$.

• The answer is $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$.

Sample 2.

• All legal subsequences are $\{2\}, \{3\}, \{4\}, \{2,3\}, \{3,4\}, \{2,4\}, \{2,3,4\}$. The answer is $407 \mod 114 = 65$.

Constraints.

Test point ID	$n \le$	Special property
$1 \sim 4$	$20$	None
$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$		None
$23 \sim 25$	$10^6$

• For $100\%$ of the testdata, $0 \le k < n \le 10^6$, $1 \le a_i \le 10^9$, $1 \le mod \le 10^9+7$.

Translated by ChatGPT 5