#442. 关系和睦

关系和睦

描述

猫猫AA和猫猫BB原本是关系很好的猫猫,但是突然有一天,两只猫猫都宣布以后所有活动再也不与对方排在一起(即位置上相邻),一旦把他们放在一起的话就会跑掉。猫猫头很纳闷,想知道将所有猫猫排成一排或环形队伍后有多少种让猫猫AA和猫猫BB不逃跑的可能。

输入格式

给定样例数量 T (1T105)T\ (1\le T\le10^5)

对于每个样例,占一行,每行给出一个字符串S (S{Line,Cycle})S\ (S\in\{Line,Cycle\})一个正整数n (1n107)n\ (1\le n \le 10^7) 按空格分隔。

输出格式

对于每个样例,输出给定 nn 个猫猫时(猫猫AA和猫猫BB总是到场的),输出有多少种猫猫AA和猫猫BB不逃跑的可能数,可能数会很大,请将结果对 998244353998244353 取模后输出。

样例

input

4
Line 3
Cycle 4
Cycle 5
Line 5

output

2
2
12
72

提示

对于第一个样例,第三个猫猫只能排中间,A,BA,B排两边因此共有两种可能。

对于第二个样例,围起来看,保证不同位置上看能够完全不相同的,仅仅是第三第四的猫猫互相交换位置,也等价于A,BA,B猫猫互相交换位置。因此也仅有两种可能。