Problem Background

As the only problem with a background, this problem is an extension based on @Ecrade_'s original problem "Subset".

"Subset" is the case where $k = n - 1$ in this problem.

Problem 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 $$

A subsequence of $x$ elements from sequence $a$ is represented as $s = \{a_{p_1}, a_{p_2}, ..., a_{p_x}\}$, where $p$ is a strictly monotonically increasing sequence, $1 \le p_1 \le p_x \le n$.

Given an integer $k$, a valid subsequence $s$ with $x$ elements from sequence $a$ must satisfy $p_x - p_1 \le k$.

Find the sum of values of all valid subsequences of sequence $a$ modulo $mod$.

Input Format

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

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

Output Format

Output a single integer representing the answer modulo $mod$.

Sample Input and Output

Sample Input #1

4 1 1000000007
1 2 3 4

Sample Output #1

150

Sample Input #2

3 2 114
2 3 4

Sample Output #2

65

Sample Input #3

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

Sample Output #3

2797740

Notes

Large Sample Data

Sample Explanation:

Sample 1:

• All valid 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 valid subsequences are $\{2\}, \{3\}, \{4\}, \{2, 3\}, \{3, 4\}, \{2, 4\}, \{2, 3, 4\}$, the answer is $407 \mod 114 = 65$.

Data Range:

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

见题面 Input 部分

见题面 Output 部分