### 问题描述 小夜有一个只包含字符 "*"，"4" 和 "0" 的字符串 $S$。 字符 "*" 可以被替换为 "4" 或 "0"。 小夜想要知道，在所有可能的由 "*" 替换得到的字符串中，子序列 "404" 的总数量是多少。由于答案可能非常大，所以请你将答案对 $10^9 + 7$ 取模后输出。 ### 输入格式 第一行输入一个整数 $T$，表示测试用例的数量。 每个测试用例包含两行： - 第一行输入一个整数 $N$，表示字符串的长度。 - 第二行输入一个长度为 $N$ 的字符串 $S$。 ### 输出格式 对于每个测试用例，输出一行，表示在所有可能的字符串中，子序列 "404" 的数量对 $10^9 + 7$ 取模后的结果。 ### 样例输入 ```text 2 4 4*04 4 4*4* ``` ### 样例输出 ```text 4 3 ``` ### 评测数据范围 $1 \leq T \leq 10^5$。 $1 \leq N \leq 10^5$。 $S$ 只包含字符 "*"，"4" 和 "0"。 所有测试用例中 $N$ 的和不超过 $10^5$。