#P18312. Unhappy Team
Unhappy Team
Unhappy Team
你管理一个由 个人组成的团队,成员编号为 到 。每个人对其他人的能力都有自己的看法:认为对方比自己强,或者比自己弱。不同人的看法不一定一致。
一个排名是 到 的排列 ,其中 表示排名第 的成员。 排名最好, 排名最差。排名公布后,每个人都能看到它。
某位成员的不满度,等于排在他前面、但被他认为比自己弱的成员人数。
给定 ,一次排名的分数为所有成员不满度中最大的 个数之和。从全部 个排列中等概率随机选择一个排名,请计算排名分数的期望,对 取模。
若期望写成 ,输出 ,其中 表示模 的乘法逆元。
输入格式
第一行包含整数 ,表示测试用例数。
对每个测试用例:
- 第一行包含整数 。
- 接下来 行,每行一个长为 的字符串。第 行第 个字符描述成员 对成员 的看法:
S: 认为 比自己强。W: 认为 比自己弱。X:仅在 时出现,表示成员自己。
不同方向的看法独立,不能假设矩阵对称,也不能假设 认为 弱就意味着 认为 强。
输出格式
每个测试用例输出一行一个整数,表示期望分数模 的值。
数据范围
- 。
- 。
- 每行字符串长度恰为 ,矩阵对角线上均为
X,所有非对角位置均为S或W。 - 一份输入中至多有 个测试用例满足 。
样例
输入
3
3 2
XSW
SXW
WSX
4 3
XSWS
WXSW
SSXS
SWWX
1 1
X
输出
499122178
499122179
0