思路:动态规划

1.我们知道，一个数是3的倍数 等价于 它的数位和 是 3的倍数。也就是数位和%3=0

然后我们知道0~9里有 4个%3=0的数 , 分别是0,3,6,9 3个%3=1的数 , 分别是1,4,7 3个%3=2的数 , 分别是2,5,8

所以考虑动态规划:$dp[i][j]$ 表示前i个数模3余j的方案数 转移方程: $dp[i][(j+a[i])\mod 3] += dp[i-1][j]$ , 其中a[i]表示第i个数，如果a[i]是问号，那么a[i]可以取0~9，如果a[i]不是问号，那么a[i]只能取a[i]。

题目内容

小红有一个长度为$n$的数字字符串$s$，但其中有一些数位被墨水覆盖看不清了。他现在想知道，有多少种可能的数字使得$s$是3的倍数（注意：$s$不含前导零）。

输入描述

第一行输入一个整数 $n$（$1≤n≤10^5$）代表数字字符串的长度。

第二行输入一个长度为$n$且仅由数字和$'?'$构成的字符串$s$。保证字符串不包含前导零。

输出描述

在一行上输出一个整数，代表满足是$3$的倍数的数字个数。由于答案可能很大，请将答案对（$10^9+7$）取模后输出

样例1

输入

4
12?4

输出

3