愿望幽灵

给定 $c$，设 $q_k$ 表示有一个 $2\times k$ 的矩阵，初始时所有位置均为空，要从中选出 $k$ 个位置涂上 $0,1,\dots,c$ 的数字，使得每列至多存在一个数字非 $0$ 的方案数。 每个位置只能涂上一种数字。 空的位置与染上任何一个数字的位置都是不同的。 每种数字可以出现在多个位置上。 给定 $n$，求 $q_1,q_2,\dots,q_n$ 模 $998244353$。 为了减小输出量，只需要输出它们的异或和即可。

本题有多组测试数据。 第一行，一个正整数 $T$ $(1 \le T \le 5)$ 表示数据组数。 对于每组数据，第一行两个整数 $n,c$ $(1 \le n \le 10^7,0 \le c < 998244353)$。

对于每组数据，一行一个非负整数，表示 $q_1,q_2,\dots,q_n$ 模 $998244353$ 后的异或和。

对于第一组数据： 异或前的结果为 [2, 6, 20, 70, 252]。 对 q[1]，考虑将第 1 行第 1 列的格子或第 2 行第 1 列的格子涂上 0 即可。 对 q[2]，考虑任意选出两个格子涂上 0 即可。 对于第二组数据： 异或前的结果为 [4, 22, 136]。 对 q[1]，考虑将第 1 行第 1 列的格子或第 2 行第 1 列的格子涂上 0 或 1 即可。 对于第三组数据： 异或前的结果为 [6, 46, 396]。