题目描述

谷米莱莉娅正在研究二进制哈希。具体来说是这样的：

她现在有一个长度为$n$的数组，每个元素用$a_i$表示。她把这些数当作每个位置的哈希模数。现在，她要使用她的真随机魔法，从$\mathbb Z\cap[0,2^{19260817}-1]$中独立且均匀随机地抽取$n$个数，这些数用$b_i$表示。她想知道，对于给定的数组$a_i$和一个数$x$，满足$\bigvee_{i=1}^n(a_i\wedge b_i)=x$的概率有多少。

其中，$\bigvee$表示将枚举的所有数按位或，例如$2$与$3$的按位或结果是$3$，而$4$与$3$的按位或结果是$7$；$\wedge$表示按位与，例如$2$与$3$的按位与结果是$2$，而$4$与$3$的按位与结果是$0$。

输入格式

输入第一行包含两个整数$n,x$。

接下来一行，包含$n$个整数，表示$a_i$。

输出格式

输出第一行包含一个整数，表示所求的概率对$998244353$取模的结果。

样例

2 3
2 1

748683265

$\frac 14\equiv 748683265\pmod{998244353}$。

数据范围

对于$30\%$的数据，$n\le 5,a_i\le 7$。

对于$100\%$的数据，$1\le n\le 10^6,0\le a_i<2^{30},0\le x<2^{30}$。

提示

如果你较少接触算法竞赛题目，可以忽略本题的背景，它对做题并没有什么帮助。

由费马小定理可得，质数模数意义下的分数