问题 B: 一次买够

在繁华的 *Anno 妙妙屋*，店主 Anno 经营着一家出售 $ n $ 种独特商品的商店，每种商品价格为 $ a_i $，且库存无限。
一天，共有 $ Q $ 位顾客光顾，每位顾客购买了一件商品。顾客按顺序购买，具体规则为：第 $ i $ 个顾客（下标从 $ 0 $ 开始）购买第 $ i \mod n $ 种商品（下标从 $ 0 $ 开始）。为了保护营业数据，Anno 在每天打烊后使用一个加密程序生成账单的加密结果。然而，今天生意太火爆，原始的加密程序运行缓慢。Anno 希望你优化她的程序，以便更快完成加密，回家练习吉他！
加密方法基于顾客集合的子集价值：
- 定义全集 $ U = \{0, 1, \dots, Q-1\} $，表示所有顾客的编号。
- 每位顾客 $ i $ 购买的商品价格为 $ A[i] $，其中 $ A[i] = a_{i \mod n} $.
- 对于集合 $ S \subseteq U $，其价值定义为 $ F(S) = \left( \prod_{i \in S} A[i] \right) \mod P $。如果 $ S $ 为空集，$ F(S) = 1 $.
- 计算 $ res[i] $，表示 $ U $ 的子集中有多少个集合 $ S $ 满足 $ F(S) = i $，结果对 $ 998244353 $ 取模。
- 最终加密结果 $ ans $ 为 $ res[i] $（对所有 $ 0 \leq i < P $）的异或和。
---
为了方便理解，她还贴心的把 naive 的加密程序发给了你：
```cpp
const int mod = 998244353;
int Q, P;
// 商品种类数和商品价格
int n, a[n];
// A[i] 表示第 i 个顾客买的商品价格
int A[Q];
// 定义集合 $S$ 的价值 $ F(S) = (\prod\limits_{i\in S}A_i) \mod P$ ，如果 $S$ 是空集，$ F(S)=1 $ 。
// 定义全集 U={0, 1, ..., Q-2, Q-1}
// res[i] 表示 U 的子集中多少个集合价值为 i，并且 res[i] 是膜 mod 后的值
int res[P];
// 枚举顾客集合的子集，i_为集合中的元素，集合的价值为 A[i] 的乘积
void dfs(int i, int prod) {
if (i == Q) {
res[prod] = (res[prod] + 1) % mod;
return;
}
dfs(i + 1, prod * A[i] % P);
dfs(i + 1, prod);
}
int main(int argc, char* argv[]) {
// 为了防止输入过大带来的常数问题，C++ 选手请尽量使用
// 关闭流同步的 `std::cin` 和 `std::cout` 实现输入输出，
// 否则可能出现因读入输出问题导致的 TLE 等。
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cin >> n >> Q >> P;
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
for (int i = 0; i < Q; i++) {
A[i] = a[i % n];
}
dfs(0, 1);
int ans = 0;
for (int i = 0; i < P; i++)
ans ^= res[i];
std::cout << ans << '\n';
return 0;
}
```