查找 404

题目描述

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

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

例如，当 $S$ 为 4*4* 时，可以替换为 4040, 4044, 4440, 4444，其中分别有 $1, 2, 0, 0$ 个 404 子序列，共 $3$ 个。

输入格式

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

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

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

输出格式

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

数据范围

• 对于 $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$ 中仅包含 4、0 和 * 三种字符

样例

样例输入

2
4
4*04
4
4*4*

样例输出

4
3

说明

第二组数据即为题目描述中举的例子。