1 Description

给定正整数 $n$、$k$、$V$ 和长度为 $n$ 的序列 $a$，你需要求出：

$$\sum\limits_{x=0}^V \sum\limits_{i=1}^n \sum\limits_{j=i+1}^n [\gcd\{a_1,a_2,\dots,a_i,a_j,a_{j+1},\dots,a_n\}^k \oplus x] \times (a_i + a_j) \bmod 998244353$$

其中 $\oplus$ 表示按位异或。

2 Input

第一行三个整数 $n$、$k$ 和 $V$；第二行 $n$ 个整数表示 $a$。

3 Output

第一行一个整数表示答案。

4 Sample

Input #1

3 2 3
3 6 2

Output #1

132

Input #2

7 8 9
1 9 1 9 8 1 1

Output #2

8100

Input #3

20 100 30
45 15 15 15 15 15 15 15 15 15 15 15 15 15 5 5 5 249266911 541438343 326852639

Output #3

261815456

5 Limitation

本题采用捆绑测试。你只有通过了一个子任务的所有测试点才能获得该子任务的分数。

对于所有数据，满足 $1 \le n \le 5 \times 10^5$、$1 \le a_i \le 2^{30}$、$0 \le V \le 10^9$ 且 $0 \le k \le 100$。

子任务编号	$n \le$	$k \le$	$V \le$	$a_i \le$	分值
$1$	$100$	$2$	$100$	$2^{30}$	14
$2$		$100$			7
$3$	$10^5$	$0$	$10^9$		11
$4$		$100$	$0$		24
$5$		$2$	$10^9$		19
$6$		$100$			14
$7$	$5 \times 10^5$				11