来源：张老师 2026 CSP-J 4＋1 拓展题 20 套；第 05 套，第 5 题。原题标号：E；原本地编号：Z4P1-05-E。

问题描述

给定长度为 $N$ 的序列 $a$ 和定值 $k,p$，对于一个序列 $b$，其权值为$\lfloor \frac{\sum_{i=1}^{|b|} b_i}{k} \rfloor$。

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

输入格式

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

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

输出格式

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

样例输入

3 3 9
1 2 1

样例输出

3

样例解释

子序列 $\{a_1\}$ 的和为 $1$，贡献为 $0$。

子序列 $\{a_2\}$ 的和为 $2$，贡献为 $0$。

子序列 $\{a_3\}$ 的和为 $1$，贡献为 $0$​。

子序列 $\{a_1,a_2\}$ 的和为 $3$，贡献为 $1$。

子序列 $\{a_1,a_3\}$ 的和为 $2$，贡献为 $0$​。

子序列 $\{a_2,a_3\}$ 的和为 $3$，贡献为 $1$。

子序列 $\{a_1,a_2,a_3\}$ 的和为 $4$，贡献为 $1$。

所以答案为 $3$。

评测数据规模

对于 $20\%$ 的数据，$1 \leq N,k \leq 20$

对于 $40\%$ 的数据，$1 \leq N,k \leq 100$​

对于另外 $40\%$ 的数据，$\gcd(k,p)=1$

对于所有测评数据，$1 \leq N,k \leq 5000,1 \leq a_i,p <998244354$。