#442. 关系和睦
关系和睦
描述
猫猫和猫猫原本是关系很好的猫猫,但是突然有一天,两只猫猫都宣布以后所有活动再也不与对方排在一起(即位置上相邻),一旦把他们放在一起的话就会跑掉。猫猫头很纳闷,想知道将所有猫猫排成一排或环形队伍后有多少种让猫猫和猫猫不逃跑的可能。
输入格式
给定样例数量
对于每个样例,占一行,每行给出一个字符串一个正整数 按空格分隔。
输出格式
对于每个样例,输出给定 个猫猫时(猫猫和猫猫总是到场的),输出有多少种猫猫和猫猫不逃跑的可能数,可能数会很大,请将结果对 取模后输出。
样例
input
4
Line 3
Cycle 4
Cycle 5
Line 5
output
2
2
12
72
提示
对于第一个样例,第三个猫猫只能排中间,排两边因此共有两种可能。
对于第二个样例,围起来看,保证不同位置上看能够完全不相同的,仅仅是第三第四的猫猫互相交换位置,也等价于猫猫互相交换位置。因此也仅有两种可能。