小欧字符串

题解思路

本题要求统计将字符串中问号替换为数字后，使得整个数字是3的倍数的方案数（注意替换后数字不含前导零）。

• 关键点：
  1. 一个数字是否是3的倍数，可以通过判断其各数位之和是否为3的倍数。
  2. 固定数字部分的和可以直接求出，再加上问号部分替换后所贡献的数位和。
  3. 对于问号的替换，采用数位DP思想：
     • 定义 dp[j] 表示经过若干个问号替换后，问号部分数位和模3为 j 的方案数。
     • 注意首位如果为问号，则只能替换成1到9（避免前导零）；其余位置允许填0~9。

题目内容

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

输入描述

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

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

输出描述

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

样例1

输入

4
12?4

输出

3

说明

可能的结果有$1224、1254、1284$这三种。

样例2

输入

10
??????????

输出

999999986

说明

答案为$3\ 000\ 000\ 000$ ，对($10^9+7$)取模后得到$999\ 999\ 886$