T463909 城市道路

A 国一共有 $N$ 个城市，编号分别为 $1,2,3,\ldots,N$。 在国家建立之初，政府需要给这 $N$ 个城市之间修一些道路。A 国的国王很喜欢二进制，他首先给每个城市一个数字，第 $i$ 个城市的数字是 $A_i$。之后，对于任意两个城市 $i, j$（$i < j$），他会从城市 $i$ 往城市 $j$ 连接 $\operatorname{popcount}(A_i \mathbin{\&} A_j)$ 条**单向**路径。各个符号的含义见题面末尾。 现在国王想知道：从城市 $1$ 出发前往城市 $N$，一共有多少条路径？由于答案可能会很大，你需要输出答案对 $998244353$ 取模后的值。

无

无

**【样例解释】** 对于第一组数据，城市道路图如下：  一共有 $4$ 条路径： - $1 \to 2 \to 4$ - $1\to 3 \to 4$ - $1\to 2 \to 3 \to 4$ - $1\to 2 \to 3 \to 4$ 对于第二组数据，$1 \sim 4$ 号城市都与城市 $5$ 没有单向道路，所以路径数是 $0$。 --- **【提示】** $\operatorname{popcount}(x)$ 表示 $x$ 的二进制表示中 $1$ 的个数。例如 $11$ 的二进制表示为 $1011_2$，故 $\operatorname{popcount}(11) = 3$。 $\mathbin{\&}$ 表示二进制与运算。二进制与运算的规则是，只有当两个数的对应位都为 $1$ 时，结果才为 $1$；否则结果为 $0$。例如下面的运算： ```plain | 01010101| |& 01111000| |----------| | 01010000| ``` 即 $85 \mathbin{\&} 120 = 80$。 --- **【数据范围】** 对于 20% 的数据，$N \le 5$，$A_i \le 7$。 对于 50% 的数据，$N \le 1000$。 对于 100% 的数据，$1\le N \le 2\times 10^5$，$1\le A_i < 2^{30}$，$1\le T \le 5$。