解题思路

设最终听到的序列为字符串 $s$（仅含 L/R）。一次击打会产生 1 个或 2 个相同字母：

• 左鼓：产生 L 或 LL；右鼓：产生 R 或 RR。

观察可知：一次击打不会跨越字母种类边界，因此答案对每个由相同字符组成的连续段（run） 彼此独立，再把每段的方案数相乘即可。

对一个长度为 $k$ 的 L（或 R）连续段，我们要把它切分成若干块，每块长度只能是 1 或 2（分别代表一次击打发出 1 个或 2 个相同的声）。 这正是典型的 1/2 划分计数，令 $f[i]$ 表示长度为 $i$ 的连续段的切分方案数，则

题目内容

在这个世界里，有左右两个大鼓。对左鼓的击打记为 "$L$"，对右鼓的击打记为 "$R$"。有趣的是，一次击打可能发出一次声音，也可能因为共鸣而发出两次相同的声音：

• 一次左鼓击打要么发出 "$L$"，要么发出 "$LL$"；
• 一次右鼓击打要么发出 "$R$"，要么发出 "$RR$"。

你只记录到了最终听到的声音序列s (仅由字符 '$L$' 和 '$R$' 组成)。请问，有多少种原始的击打序列 $p$ 能产生该声音序列？

输入描述

第一行包含一个整数 $t(1≤t≤10^5)$，表示测试用例数。 接下来 $t$ 行，每行包含一个非空字符串 $s$ ，由字符 '$L$' 和 '$R$' 组成，长度记为 $∣s∣$ 。 保证所有测试用例中 $∑∣s∣≤2×10^5$。

输出描述

对于每个测试用例，输出一行，包含一个整数——能产生该声音序列的击打序列总数。 由于答案可能很大，请对 $10^9+7$ 取模后输出。

样例1

输入

5
LR
LLRR
LRLR
L
RRR

输出

1
4
1
1
3

说明

LR:

• 左鼓击打一次发出 L，右鼓击打一次发出 R;
• 只有一种击打序列 LR。

LLRR:

• 左鼓击打一次发出 LL，右鼓击打一次发出 RR;
• 左鼓击打两次各发出 L，右鼓击打一次发出 RR;
• 左鼓击打一次发出 LL，右鼓击打两次各发出 R;
• 左鼓击打两次各发出 L，右鼓击打两次各发出 R;
• 共 4 种击打序列。

RRR:

• 右鼓击打一次发出 RR，右鼓击打一次发出 R;
• 右鼓击打一次发出 R，右鼓击打一次发出 RR;
• 右鼓击打三次各发出 R;
• 共 3 种击打序列。