sylvia 是一个擅长唱歌的女孩子，这天她决定要教 $n$ 个小学生如何唱歌。

在精心挑选后，sylvia 找到了一首简单好听的歌曲 $s$，这首歌曲有 $m$ 个音，每一个音的音高用一个小写字母来表示，即可以理解为这首歌曲是一个长度为 $m$ 的小写字符串。

最开始，sylvia 让这些小学生从小到高排成一排，第 $i$ 个小学生标号为 $i$。为了让合唱显得整齐，她想要从这个队列中，挑出连续的长度为 $m$ 的一段 $[L,L+m-1]$ 来进行一次合唱表演：首先第 $L$ 个小学生唱第 $1$ 个音，接着第 $L+1$ 个小学生唱第 $2$ 个音，$\dots$，最后第 $L+m-1$ 个小学生唱第 $m$ 个音。

然而，所有小学生都是五音不全的咸鱼，什么音都不会唱。

为了教会小学生如何唱歌，sylvia 设计了若干个课程，其中第 $i$ 个课程为“教第 $a_i$ 小学生唱第 $b_i$ 个音”，并决定用如下的形式进行教学：

每一次，sylvia 会在所有课程中等概率挑选一个课程进行（即使这个课程已经进行过了），在这个课程结束时，第 $a_i$ 个小学生就学会了如何唱第 $b_i$ 个音。

当然，sylvia 也是一个小懒惰的女孩子。当她发现队列中存在一个区间 $[L,L+m-1]$ 满足对于所有 $i \in [1,m]$，第 $L+i-1$ 个熊孩子都已经学会了唱第 $s_i$ 个音时，她就会停止教学 —— 因为合唱已经可以顺利进行啦。

现在，sylvia 想要知道她需要上的课程数的期望是多少？

输入格式

输入第一行一个正整数 $T$，表示数据组数。

对于每组数据，第一行两个正整数 $n,m$ 表示小学生数目和歌曲长度。保证 $1 \leq m \leq n$。

接下来 $n$ 行，每行一个不包含重复小写字母的字符串 $t_i$，其中字符串的每一位 $t_{i,j}$ 都表示存在一个课程是教第 $i$ 个小学生如何唱音 $t_{i,j}$。

接下来一行一个长度为 $m$ 的小写字符串，表示歌曲的内容。

输出格式

对于每组数据输出一行，一个整数，表示答案。由题目性质知，期望一定可以写成 $\frac{p}{q}$ 形式的有理数，请输出期望对 $998244353$（$7 \times 17 \times 2^{23} + 1$，一个质数） 取模后的结果，即找出一个 $x$ （$0 \leq x < 998244353$） 使得 $qx \equiv p \pmod{998244353}$。显见这样的 $x$ 是唯一的。

如果无论如何 sylvia 的教学都不会结束，那么输出 -1。

样例一

input

1
1 1
ab
a

output

2

explanation

第一节课上完就结束的概率是 $\frac{1}{2}$，第二节课上完结束的概率是 $\frac{1}{4}$，第 $i$ 节课上完结束的概率是 $\frac{1}{2^i}$。

所以答案是 $\sum_{i=1}^\infty \frac{i}{2^i}=\sum_{i=1}^\infty \frac{1}{2^{i-1}}=2$

样例二

input

1
3 2
acb
cb
ab
cb

output

915057330

样例三

见样例数据下载，限制与约定跟第 $4$ 个测试点相同。

样例四

见样例数据下载，限制与约定跟第 $7$ 个测试点相同。

限制与约定

对于所有数据，$T \leq 5$

时间限制：$2\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载