#P18312. Unhappy Team

Unhappy Team

Unhappy Team

你管理一个由 NN 个人组成的团队,成员编号为 11 到 NN。每个人对其他人的能力都有自己的看法:认为对方比自己强,或者比自己弱。不同人的看法不一定一致。

一个排名是 11 到 NN 的排列 PP,其中 PiP_i 表示排名第 ii 的成员。P1P_1 排名最好,PNP_N 排名最差。排名公布后,每个人都能看到它。

某位成员的不满度,等于排在他前面、但被他认为比自己弱的成员人数。

给定 KK,一次排名的分数为所有成员不满度中最大的 KK 个数之和。从全部 N!N! 个排列中等概率随机选择一个排名,请计算排名分数的期望,对 998244353998244353 取模。

若期望写成 AB\frac{A}{B},输出 A⋅B−1 mod 998244353A\cdot B^{-1}\bmod998244353,其中 B−1B^{-1} 表示模 998244353998244353 的乘法逆元。

输入格式

第一行包含整数 TT,表示测试用例数。

对每个测试用例:

  • 第一行包含整数 N,KN,K。
  • 接下来 NN 行,每行一个长为 NN 的字符串。第 ii 行第 jj 个字符描述成员 ii 对成员 jj 的看法:
    • S:ii 认为 jj 比自己强。
    • W:ii 认为 jj 比自己弱。
    • X:仅在 i=ji=j 时出现,表示成员自己。

不同方向的看法独立,不能假设矩阵对称,也不能假设 ii 认为 jj 弱就意味着 jj 认为 ii 强。

输出格式

每个测试用例输出一行一个整数,表示期望分数模 998244353998244353 的值。

数据范围

  • 1≤T≤501\le T\le50。
  • 1≤K≤N≤161\le K\le N\le16。
  • 每行字符串长度恰为 NN,矩阵对角线上均为 X,所有非对角位置均为 S 或 W。
  • 一份输入中至多有 33 个测试用例满足 N>12N>12。

样例

输入

3
3 2
XSW
SXW
WSX
4 3
XSWS
WXSW
SSXS
SWWX
1 1
X

输出

499122178
499122179
0