Given is a string SS. Each character in SS is either a digit (0, ..., 9) or ?.

Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 55 when divided by 1313? An integer may begin with 00.

Since the answer can be enormous, print the count modulo 109+7109+7.

Constraints
SS is a string consisting of digits (0, ..., 9) and ?.
1≤|S|≤1051≤|S|≤105
Input
Input is given from Standard Input in the following format:

SS
Output
Print the number of integers satisfying the condition, modulo 109+7109+7.

??2??5
768

?44
1

7?4
0

?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???
153716888

题意:给你一个字符串,字符串的内容只包含0-9和字符?,其中?代表你可以填写0-9中的任意一个,字符串中已经填写0-9的不能更该。问该字符串有多少种填法,是除与13余5 %13 = 5

dp[i][j] 表示前1-i位置中余数为j的方案数

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int dp[maxn][13];
char str[maxn];
int main() {
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    if (str[1] == '?') {
        for (int i = 0; i <= 9; i++) {
            dp[1][i] = 1;
        }
    } else {
        dp[1][str[1] - '0'] = 1;
    }
    for (int i = 2; i <= n; i++) {
        if (str[i] == '?') {
            for (int j = 0; j <= 9; j++) {  //当前位置 
                for (int k = 0; k <= 12; k++) { //上一个位置 
                    int t = (k * 10 + j) % 13;
                    dp[i][t] = (dp[i][t] + dp[i - 1][k]) % mod;
                }
            }
        } else {
            for (int k = 0; k <= 12; k++) {
                int t = (k * 10 + (str[i] - '0')) % 13;
                dp[i][t] = (dp[i][t] + dp[i - 1][k]) % mod;
            }
        }
    }
    printf("%d\n", dp[n][5]);
    return 0;
}