小欧字符串
题解思路
本题要求统计将字符串中问号替换为数字后，使得整个数字是3的倍数的方案数（注意替换后数字不含前导零）。
- 关键点：
- 一个数字是否是3的倍数，可以通过判断其各数位之和是否为3的倍数。
- 固定数字部分的和可以直接求出，再加上问号部分替换后所贡献的数位和。
- 对于问号的替换，采用数位DP思想：
- 定义 dp[j] 表示经过若干个问号替换后，问号部分数位和模3为 j 的方案数。
P2703.第3题-小欧字符串
题目内容
小欧有一个长度为n的数字字符串s，但其中有一些数位被墨水覆盖看不清了。他现在想知道，有多少种
可能的数字使得s是3的倍数(注意:s不含前导零)。
输入描述
第一行输入一个整数n(1≤n≤105)代表数字字符串的长度。
第二行输入一个长度为n且仅由数字和'?'构成的字符串s。保证字符串不包含前导零。
输出描述
在一行上输出一个整数，代表满足是3的倍数的数字个数。由于答案可能很大，请将答案对(109+7)取模后输出。
样例1
输入
4
12?4
输出
3
说明
可能的结果有1224、1254、1284这三种。
样例2
输入
10
??????????
输出
999999986
说明
答案为3 000 000 000 ，对(109+7)取模后得到999 999 886
