修复密文
题解思路
本题要求统计将字符串中问号替换为数字后，使得整个数字是3的倍数的方案数（注意替换后数字不含前导零）。
- 关键点：
- 一个数字是否是3的倍数，可以通过判断其各数位之和是否为3的倍数。
- 固定数字部分的和可以直接求出，再加上问号部分替换后所贡献的数位和。
- 对于问号的替换，采用数位DP思想：
- 定义 dp[j] 表示经过若干个问号替换后，问号部分数位和模3为 j 的方案数。
题目内容
一位探险家在古墓中发现了一串长度为 n 的密文，密文由数字和模糊不清的占位符 ‘?’ 组成，其中 ‘?’ 表示该位置的数字已无法辨认。已知这串密文代表的整数没有前导零，即第一位不能是 ‘0’。探险家想知道，在所有将 ‘?’ 替换为数字（若在首位则只能替换为 ‘1’ 到 ‘9’）的方案中，有多少种方案得到的整数是 3 的倍数。
给定密文的长度 n 以及密文字符串，请你计算满足条件的方案总数。由于答案可能很大，你需要将答案对 109+7 取模后输出。
字符串的长度 n 不超过 105，字符串仅由数字字符和 ‘?’ 构成，且给出的部分不会使首位成为 ‘0’。
输入描述
第一行包含一个整数 n，表示密文的长度。
