题目描述

听说摆一个同时有 $\sum$ 和 $\prod$ 的式子可以吓跑 99% 的人。

给定一个长为 $n$ 的序列 $\{a_i\}$ 和两个整数 $k,m$。

求所有长度不超过 $k$ 的子段的元素乘积之和。答案对 $m$ 取模。换言之，求

$$\left( \sum_{l=1}^{n} \sum_{r=l}^{\min(l+k-1,n)} \prod_{i=l}^r a_i \right) \bmod m$$

输入格式

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 组数据，每组第一行三个整数 $n,k,m$。

接下来一行 $n$ 个整数，第 $i$ 个代表 $a_i$。

输出格式

共 $T$ 行，每行一个整数，表示答案对 $m$ 取模的值。

3
5 3 7
1 2 3 4 5
1 1 45
9
5 1 4
1 9 1 9 8

5
9
0

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 400$，$1 \le n \le 500$；
• 对于 $60\%$ 的数据，$m = 2$；
• 对于 $100\%$ 的数据，$1 \le T \le 2 \cdot 10^5$，$1 \le n, \sum n \le 2 \cdot 10^5$，$0 \le a_i \le 10^9$，$2 \le m \le 10^9$。