### 问题描述 大衣遇到一个只包含 $4​$，$0​$，$*​$ 这三种字符的字符串，$*​$ 可以代表一个 $4​$ 或者一个 $0​$，大衣想知道可能的字符串中子序列为 $404​$ 的个数的总和。 例如：$4*04$ 可以表示成 $4404$ 和 $4004$ 两个字符串： - $4004$ 中有两个 $404$ 子序列：$S_1S_2S_4$ 和 $S_1S_3S_4$。 - $4404$ 中有两个 $404$ 子序列：$S_1S_3S_4$ 和 $S_2S_3S_4$。 答案可能很大，将答案对 $10^9+7​$ 取模。 ### 输入格式 第一行输入一个正整数 $N​$ 表示字符串的长度。 第二行输入一个长度为 $N$ 的字符串 $S​$。 ### 输出格式 输出一个数字表示答案，由于答案可能很大，将其对 $10^9+7​$ 取模。 ### 样例输入1 ```text 4 4*04 ``` ### 样例输出1 ```text 4 ``` ### 样例输入2 ```text 4 4*4* ``` ### 样例输出2 ```text 3 ``` ### 说明 - 样例 $1$ 所有可能的 $404$ 字符串为： - $4004​$ 中有两个：$S_1S_2S_4​$ 和 $S_1S_3S_4​$。 - $4404​$ 中有两个：$S_1S_3S_4​$ 和 $S_2S_3S_4​$。 所以 $404$ 的总个数为 $4​$ 。 - 样例 $2$ 所有可能的 $404$ 字符串为： - $4040​$ 中有一个：$S_1S_2S_3​$​。 - $4044$ 中有两个：$S_1S_2S_3$ 和 $S_1S_2S_4$。 所以 $404​$ 的总个数为 $3​$ 。 ### 评测数据规模 对于所有的评测数据，$1\le N\le 2\times10^5$，$S_i$ 是 $4$，$0$，$*​$ 其中一种。