Problem

Given a Salesforce workflow configuration string config consisting of digits (0-9) and placeholders (?), determine the number of ways the placeholders can be replaced with digits (0-9) such that no two adjacent workflow steps (digits) are the same.

Input

The workflow configuration string consisting of digits (0-9) and placeholders (?).

Output

The total number of valid configurations modulo (10^9 + 7).

Example

Given the workflow configuration string config = "1?3?":

• The first placeholder (?) can be replaced with 8 possible digits: {2, 4, 5, 6, 7, 8, 9, 0} (all digits except 1 and 3).
• The second placeholder can be replaced with 9 possible digits: {1, 2, 4, 5, 6, 7, 8, 9, 0} (all digits except 3). This results in a total of 72 possible configurations. Since the total number of configurations may be very large, return the result modulo (10^9 + 7).

Constraints

• 1 ≤ |config| ≤ 10^5
• The string config consists of digits from '0' to '9' and '?' only.