题目背景

题目描述

给定长度为 $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$。

本站补充：原套别：第 14 套 B 题。