题目描述

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

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

例如，当 $S$ 为 $x*x*$ 时，可以替换为 $xlxl, xlxx, xxxl, xxxx$，其中分别有 $1, 2, 0, 0$ 个 $xlx$ 子序列，共 $3$ 个。

输入格式

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

• 第一行一个整数 $n$ 表示 $S$ 的长度。
• 第二行一个字符串 $S$。

输出格式

对于每组数据，输出一行一个整数表示答案，结果对 $10^9+7$ 取模。

数据范围

• 对于 30% 的数据：$1 \leq T \leq 5$，$n \leq 10$。
• 对于 60% 的数据：$1 \leq T \leq 5$，$n \leq 100$。
• 对于 100% 的数据：$1 \leq T \leq 5$，$n \leq 10^6$，$S$ 中仅包含 $x$、$l$ 和 $*$ 三种字符。

样例输入

2
4
x*lx
4
x*x*

样例输出

4
3