#P18603. Count Hamiltonian Cycles

Count Hamiltonian Cycles

Count Hamiltonian Cycles

给出长度为 2n2n 的字符串 ss,其中恰有 nn 个 W 和 nn 个 B。依次把字符位置编号为 1,2,…,2n1,2,\ldots,2n,并据此建立无向图:两个位置颜色不同时连一条边,其权值为下标距离 ∣i−j∣|i-j|;同色位置之间没有边。

请统计总边权最小的哈密顿环有多少个,答案对 998244353998244353 取模。哈密顿环访问每个顶点恰好一次并回到起点,总权值为环中所有边权之和。

按无向边的集合区分环:仅改变起点或遍历方向不算新环。这里的边权是线性下标之差,不是把字符串绕成圆后的最短距离。

输入格式

第一行是测试用例数 tt,1≤t≤1041\le t\le10^4。

每组先给出整数 nn,2≤n≤1062\le n\le10^6;下一行是长度为 2n2n 的字符串,恰含 nn 个 W 和 nn 个 B。所有用例的 nn 之和不超过 10610^6。

输出格式

每组输出一个整数,表示最短哈密顿环的数量模 998244353998244353。

样例输入 1

3
2
WWBB
3
WBWBWB
7
WWWWBWBBWWBBBB

样例输出 1

1
2
62208

样例说明

第一组只有四条边,唯一无向环可沿 1→3→2→4→11\to3\to2\to4\to1 遍历。沿相反方向走得到相同的边集,仍只计一次。