You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

有一个字符串 $S$，该字符串仅由字符 *、S 和 O 组成。字符 * 可以被替换为 S 或 O。

藤藤想要计算在所有可能通过替换 * 生成的字符串中，包含子序列 SOS 的总数。由于这个数字可能非常大，你需要其输出模 $10^9+7$ 的结果。

例如，当 $S$ 为 S*S* 时，可以替换为 SOSO,SOSS,SSSO,SSSS，其中分别有 $1,2,0,0$ 个 SOS 子序列，共 $3$ 个。

Format

Input

第一行一个整数 $T$ 表示数据组数。对于每组数据：

第一行一个整数 $n$ 表示 $S$ 的长度。

第二行一个字符串 $S$。

Output

对于每组数据，输出一行一个整数表示答案。

Samples

样例输入

2
4
S*OS
4
S*S*

样例输出

4
3

Limitation

对于 $30\%$ 的数据，$1 \leq T \leq 10, 1 \leq n,\sum n \leq 10$

对于 $60\%$ 的数据，$1 \leq T \leq 100, 1 \leq n, \sum n \leq 100$

对于 $100\%$ 的数据，$1 \leq T \leq 10^5, 1 \leq n \leq 10^5, 1 \leq \sum n \leq 10^6$，$S$ 中仅包含 S、O 和 * 三种字符。