Description

给定长度为 $n$ 的序列 $a$ 和一个数 $t$ ，其中 $t = 1,2,3$ ，求所有 $1 \leq i < j \leq n$ 的 $a_i \oplus a_j$ 的和

若 $t = 1$ ，则 $\oplus$ 代表按位与

若 $t = 2$ ，则 $\oplus$ 代表按位或

若 $t = 3$ ，则 $\oplus$ 代表按位异或

由于答案过大，你只需要输出答案对 998244353 取模的结果

Input

第一行两个正整数 $n,t$

第二行 $n$ 个正整数，代表序列 $a$

Output

一行一个正整数，表示答案

Limitation

对于 $100\%$ 的数据，$1 \leq n \leq 10^6,0 \leq a_i < 2^{31} ,t =1,2,3$

特殊性质： $0 \leq a_i \leq 1$

提示：c++中按位与，按位或，按位异或的符号分别为 &,|,^ 。注意这些符号的运算优先级很低。

Sample

5 1
1 2 3 4 5

9