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

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

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

输入格式 第一行一个整数 T T 表示数据组数。对于每组数据：

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

第二行一个字符串 S S。

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

数据范围 对于 30 % 30% 的数据， 1 ≤ T ≤ 10 1≤T≤10， 1 ≤ n , ∑ n ≤ 10 1≤n,∑n≤10。

对于 60 % 60% 的数据， 1 ≤ T ≤ 100 1≤T≤100， 1 ≤ n , ∑ n ≤ 100 1≤n,∑n≤100。

对于 100 % 100% 的数据， 1 ≤ T ≤ 1 0 5 1≤T≤10 5 ， 1 ≤ n ≤ 1 0 5 1≤n≤10 5 ， 1 ≤ ∑ n ≤ 1 0 6 1≤∑n≤10 6 ， S S 中仅包含 4、0 和 * 三种字符。

样例数据 输入: 2 4 404 4 44* 输出: 4 3 说明: 第二组数据即为题目描述中举的例子。