Sum of Legal Subsequence Values

Given a sequence \(a\) of \(n\) integers, a subsequence \(s\) with \(x\) elements is defined as \(s = \{a_{p_1}, a_{p_2}, \dots, a_{p_x}\}\) where \(p\) is a strictly increasing sequence (i.e. \(1 \le p_1 < p_2 < \cdots < p_x \le n\)).

The value of a subsequence \(s\) is defined as:

\[ \left(\sum_{i=1}^{x} s_i\right) \times \left(\prod_{i=1}^{x} s_i\right). \]

In addition, a subsequence \(s\) is considered legal if \(p_x-p_1 \le k\), where \(k\) is a given integer. That is, the difference between the indices of the last and the first element of the subsequence cannot exceed \(k\).

Your task is to compute the sum of the values of all legal subsequences of \(a\) modulo a given integer mod.

Note: A subsequence consisting of a single element is always legal since \(p_x-p_1=0\le k\).

inputFormat

The first line contains three integers \(n\), \(k\), and mod (mod can be any positive integer).

The second line contains \(n\) integers representing the sequence \(a\): \(a_1,a_2,\dots,a_n\).

outputFormat

Output a single integer, the sum of the values of all legal subsequences modulo mod.

sample

3 1 100
1 2 3

50