时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld
题目描述
在超级猪星上，超级小猪研究员发现了一个仅由字符 P、I、G 组成的字符串 。现在需要统计其中有多少个 超级 PIG 序列。
超级小猪
一个 超级 PIG 序列 需要满足以下条件：
-
它由
个
P、个
I、个
G依次拼接而成，即形如。
-
。
-
数量关系满足：
。
你需要计算在给定的字符串 中，有多少个子序列是 超级 PIG 序列。答案对
取模。
对于一个序列，删除任意个任意位置的字符后得到的新非空序列是原序列的子序列。如 abcde 包含 abcde、ace 等子序列。
输入描述:
第一行包含一个整数
（
），表示测试数据组数。
接下来每组数据：
第一行包含一个整数
（
），表示字符串长度。
第二行包含一个长度为
，仅由大写字母P、I、G组成。
保证所有测试数据的 之和不超过
。
输出描述:
对于每组数据，输出一行一个整数，表示满足条件的子序列数量对
取模后的结果。