Problem Description

给定长度为 $N$ 的序列 $a$ 和定值 $k,p$。

对于一个序列 $b$，其权值为$\lfloor \frac{\sum_{i=1}^{|b|} b_i}{k} \rfloor$。

小 $M$ 想请你求解序列 $a$ 的所有非空子序列的权值和，答案对 $p$​​ 取模。

题目不保证模 $p$ 意义下存在 $k$ 的逆元。

Input

第一行包含 $3$ 个正整数 $N,k,p$。

第二行包含 $N$ 个正整数，第 $i$ 个表示 $a_i$。


#### 评测数据规模：

对于所有测评数据，$1 \leq N,k \leq 4321,1 \leq a_i,p \leq 987654321$。

Output

输出共 $1$ 行，输出 $1$ 个整数，表示最终答案。

3 3 9
1 2 1

3