QUESTION 1: WORKFLOW CONFIGURATION
You are given a string s containing digits from 0 to 9 and question marks (?).
Replace every question mark with a digit so that no two adjacent characters in the resulting string are equal.
Existing digits cannot be changed. Each question mark is replaced independently. Leading zeroes are allowed.
Find the number of distinct valid resulting strings. Return the answer modulo 1000000007.
INPUT
One line containing the string s.
CONSTRAINTS
1 <= length of s <= 100000
Each character is a digit or a question mark.
OUTPUT
Print the number of valid strings modulo 1000000007.
EXAMPLE 1
Input:
?2
Output:
9
Explanation:
The question mark can be any digit except 2.
EXAMPLE 2
Input:
6?0
Output:
8
Explanation:
The middle digit must differ from both 6 and 0.
EXAMPLE 3
Input:
1?3?
Output:
72
Explanation:
The first question mark has 8 choices.
The second question mark has 9 choices.
The answer is 8 * 9 = 72.