P6856 "EZEC-4.5" Subsequences

As the only problem with a background story, this problem is an extension made by the setter based on the original problem "Subset" by @[Ecrade_](https://www.luogu.com.cn/user/322075). "Subset" is exactly the case $k = n - 1$ in this problem.

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

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

Output one integer, the answer modulo $mod$.

[Large sample](https://www.luogu.com.cn/paste/5sg4ahwn) ### 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$ | None | | $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$ | None | | $23 \sim 25$ | $10^6$ | None | - 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