C1933 [Wannafly冬令营2018Day7]逆序对!(简单版)

内存限制:256 MB 时间限制:1000 ms

题目描述

给定长度为 $n$ 的两两不相同的整数数组 $b[1...n]$,定义 $f(y)$ 为:将 $b$ 每个位置异或上 $y$ 后,得到的新数组的逆序对个数。

现在你需要求 $\sum_{i=1}^{m}f(i)$

由于答案可能很大,你只需要输出答案对 $998244353$ 取模后的值

输入格式

第一行两个正整数 $n,m$ $(1\leq n\leq 10^3 , 1\leq m\leq 10^9)$

第二行 $n$ 个整数表示 $b[1...n]$ $0\leq b[i]\leq 10^9$,保证 $b[1...n]$ 互不相同

输出

输出一个数,表示答案

样例

样例输入 1

3 6 1 2 3

样例输出 1

9

提示