#P14563. 潮水啊,我已归来

潮水啊,我已归来

1 Description

给定正整数 nn、kk、VV 和长度为 nn 的序列 aa,你需要求出:

$$\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

第一行三个整数 nn、kk 和 VV;第二行 nn 个整数表示 aa。

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≤n≤5×1051 \le n \le 5 \times 10^5、1≤ai≤2301 \le a_i \le 2^{30}、0≤V≤1090 \le V \le 10^9 且 0≤k≤1000 \le k \le 100。

子任务编号 n≤n \le k≤k \le V≤V \le ai≤a_i \le 分值
11 100100 22 100100 2302^{30} 14
22 100100 7
33 10510^5 00 10910^9 11
44 100100 00 24
55 22 10910^9 19
66 100100 14
77 5×1055 \times 10^5 11