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,* 三种字符。