D. Сапер 1D
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

Игра «Сапер 1D» проходит на клетчатой полоске высотой в 1 клетку и шириной в n клеток. В некоторых из этих клеток находятся бомбы. Если в клетке бомбы нет, то в ней записано число от 0 до 2 — суммарное количество бомб в соседних клетках.

Например, корректное поле для игры может выглядеть так: 001*2***101*. Клетки, которые помечены символом «*», содержат бомбы. Обратите внимание, что на корректном поле числа обозначают количество бомб в соседних клетках. Например, поле 2* — некорректное, потому что у клетки с числом 2 должно быть две соседние клетки с бомбой.

Валера хочет создать корректное поле для игры в «Сапер 1D». Он уже нарисовал клетчатую полоску шириной в n клеток, разместил на поле несколько бомб и записал числа в некоторые клетки. Теперь его интересует, сколько существует способов так заполнить оставшиеся клетки бомбами или числами, чтобы получилось корректное поле.

Входные данные

В первой строке записана последовательность символов без пробелов s1s2... sn (1 ≤ n ≤ 106), содержащая только символы «*», «?» и цифры «0», «1» или «2». Если символ si равен «*», то i-я клетка поля содержит бомбу. Если символ si равен «?», значит Валера еще не решил, что будет находиться в i-й клетке. Символ si, являющийся цифрой, обозначает цифру, записанную в i-й клетке.

Выходные данные

Выведите одно число — количество способов, которыми Валера может заполнить свободные клетки, получив при этом корректное поле.

Так как ответ может быть очень большим, выведите его по модулю 1000000007 (109 + 7).

Примеры
Входные данные
?01???
Выходные данные
4
Входные данные
?
Выходные данные
2
Входные данные
**12
Выходные данные
0
Входные данные
1
Выходные данные
0
Примечание

В первом тестовом примере можно получить следующие корректные поля: 001**1, 001***, 001*2*, 001*10.