题目描述

给定一个正整数 $n$ 和一个非空的数码集合 $D \subset \{1,2,3,4,5,6,7,8,9\}$。

等概率随机地生成一个长度为 $2n-1$ 的算术表达式。这个表达式的构造遵循以下规则：

• 所有位于奇数位置（从 $1$ 开始计数）的字符，都将是从给定的数码集合 $D$ 中等概率随机选取的一个数码。
• 所有位于偶数位置（从 $1$ 开始计数）的字符，都将是从 $\{+,*,\wedge,\vee,\oplus\}$（加法、乘法、按位与、按位或、按位异或）中等概率随机选取的一个运算符。

例如，如果 $n=2$ 且数码集合 $D=\{1,2\}$，产生的随机表达式可以是 $1+1$、$2 \lor 1$ 等等。

计算这个随机生成表达式的值的期望，并将其结果对 $998244353$ 取模。

注意：所有运算符优先级相同，运算从左到右依次进行。

输入格式

第一行包含一个整数 $t\ (1 \leq t \leq 100)$，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n,k\ (1 \leq n \leq 10^{18}, 1 \leq k \leq 9)$。

第二行包含 $k$ 个互不相同的整数，它们是集合 $D$ 中的元素，每个元素都在 $1$ 到 $9$ 的范围内。

输出格式

对于每个测试用例，输出一行一个整数，表示表达式的值的期望对 $998244353$ 取模后的结果。

可以证明这个期望值一定可以表示为 $\frac{p}{q}$ 的形式，其中 $p$ 和 $q$ 为整数，且存在唯一的整数 $x \in [0,998244353)$ 使得 $ax \equiv p \pmod{998244353}$。你需要输出这个 $x$ 的值。

3
1 1
5
2 2
1 2
10000 9
1 2 3 4 5 6 7 8 9

5
848507702
463950893