You are given a string S. Each character in the string S is either a digit between 0 to 9(both included) or the symbol '?'.

You can perform the following operation on the string S:

• You can replace the '?' symbol with any digit from 0-9

After replacing all '?' symbol in the string S with a digit you will get an integer. The integer may start with leading zeros too.

Your task is to count the number of helpful integer generated after replacing each '?' with an integer. Since the answer can be very large, return it to modulo 10^9 + 7.

A helpful integer is defined as an integer whose remainder is equal to 7 when divided by 13 and 11.

constraints:

1 <= len( S ) <= 10^4

Sample Input 1: ??33?

Output: 10

Explanation: Possible integers are 37330,42335,46339, ...

Sample Input 2: ??????

Output: 6993

Explanation: Possible integers are 000007, 000150, 047483, ...

I came across this question and I have try to eliminate all the integers which does not give remainder 7 when divisible by 143. But doesn't look efficient since length of S is very large. So can anyone help me to give some idea about how to approach these kind of question?

I tried to solve the problem on codechef problem COINS. And I have write the following code:

#define long long LL

map<LL,LL> data;   //map DS to store key:value pair
LL solve(LL n){
    if(n<=2)
      return n;
    if(data[n]==0){
      data[n] = max(n,(solve(n/4)+solve(n/3)+solve(n/2)));
    }
    return data[n];
} 

This Link have a very nice discussion on time complexity of this code but I am not able to get any of that. can any one help me out to explain me in detail how can I approch to find the time complexity of this specific problem.

Can anyone explain why Time and memory are 0ms and 0KB. I didn't get it??