给你一个由 $N$ 个整数组成的序列 $A[1], A[2], \dots, A[N]$。同时给你一个整数 $K$ 和一个整数 $V$。

设 $\gcd(X_1, X_2, \dots, X_k)$ 表示整数 $X_1, X_2, \dots, X_k$ 的最大公约数。例如，$\gcd(14, 21) = 7$，$\gcd(4, 8, 15) = 1$。

我们定义 $f_{l,r}(x) = \gcd(A[1], A[2], \dots, A[l], A[r], A[r + 1], \dots, A[N])^K \oplus x$，其中 $\oplus$ 表示按位异或运算。你的任务是计算以下总和：

$$\left( \sum_{x=0}^{V} \sum_{l=1}^{N} \sum_{r=l+1}^{N} f_{l,r}(x) \cdot (A[l] + A[r]) \right) \bmod 998\,244\,353$$

实现细节

你需要实现一个名为 calculate_sum 的函数：

int32 calculate_sum(int32 N, int32 K, int32 V, int32[] A);

• N：序列中整数的个数；
• K：指数；
• V：$x$ 的最大值；
• A：整数序列；
• 在程序开始时，对于每个测试用例，此函数最多可能会被调用 100 次。

该函数应返回模 $998\,244\,353$ 后的总和：

$$\left( \sum_{x=0}^{V} \sum_{l=1}^{N} \sum_{r=l+1}^{N} f_{l,r}(x) \cdot (A[l] + A[r]) \right) \bmod 998\,244\,353$$

数据范围

• $1 \le N \le 5 \times 10^5$
• $0 \le K \le 100$
• $0 \le V \le 10^9$
• 对于每个 $i = 1 \dots N$，$1 \le A[i] \le 10^9$

子任务

1. Subtask 1 (4 points): $N = 1, K = 1$
2. Subtask 2 (8 points): $N \le 100, K \le 2, V \le 100$
3. Subtask 3 (15 points): $N \le 100, K \le 100, V \le 100$
4. Subtask 4 (11 points): $N \le 10^5, K = 0$
5. Subtask 5 (17 points): $N \le 10^5, V = 0$
6. Subtask 6 (21 points): $N \le 10^5, K \le 2$
7. Subtask 7 (11 points): $N \le 10^5$
8. Subtask 8 (13 points): 无附加限制。

样例

输入样例 1

3 2 3
3 6 2

输出样例 1

132

输入样例 2

7 1 0
1 2 3 4 5 6 7

输出样例 2

168

说明

样例评测程序

样例评测程序将按以下格式读取输入：

• 第 1 行：三个整数 $N$，$K$ 和 $V$
• 第 2 行：$N$ 个整数 $A[1], A[2], \dots, A[N]$

样例评测程序将调用 calculate_sum(N, K, V, A) 并输出返回值。