#P18085. Transform

Transform

Transform

题目描述

给定含 nn 个元素的可重集 S={s1,…,sn}S=\{s_1,\ldots,s_n\} 和整数 kk。

一次操作可以从 SS 中选择一个子可重集 S′S',将所选元素从 SS 中移除,然后向 SS 中加入一个数 mex⁡(S′)\operatorname{mex}(S')。允许选择空集。

这里 mex⁡\operatorname{mex} 是集合中没有出现过的最小非负整数。例如 mex⁡{0,1,2}=3\operatorname{mex}\{0,1,2\}=3,mex⁡{1,0,3,1}=2\operatorname{mex}\{1,0,3,1\}=2,mex⁡∅=0\operatorname{mex}\varnothing=0。重复元素可以分别选取或保留。

求把 SS 变成只含一个元素 kk 的可重集 {k}\{k\} 所需的最少操作次数,对 998244353998244353 取模。可以证明总存在可行方案。应先最小化实际次数,再对答案取模。

输入格式

第一行一个整数 tt。每组第一行两个整数 n,kn,k,第二行 nn 个整数 s1,…,sns_1,\ldots,s_n。

1≤t≤1051\le t\le10^5,1≤n≤5⋅1051\le n\le5\cdot10^5,0≤k,si≤1090\le k,s_i\le10^9;所有组的 nn 之和不超过 5⋅1055\cdot10^5。

输出格式

每组输出一行,表示最少操作次数对 998244353998244353 取模的结果。

样例输入

6
1 2
1
1 4
4
3 3
0 2 2
4 2
1 0 3 2
4 3
2 1 0 2
3 52
20 2 6

样例输出

2
0
3
2
1
262875292