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?
Is there anywhere I can submit my solution to this problem?
Do you understand the approach for this problem if yes can you explain me?
If you want a first hint, notice that 7, 11 and 13 are fixed, have this any meaning? Ask me for another hint if you want. This is a good aproach for a lot of problems, thinking in the reasons of the statement and why it has fixed values.
You can solve it using Digit DP.