Игра «Сапер 1D» проходит на клетчатой полоске высотой в 1 клетку и шириной в n клеток. В некоторых из этих клеток находятся бомбы. Если в клетке бомбы нет, то в ней записано число от 0 до 2 — суммарное количество бомб в соседних клетках.
Например, корректное поле для игры может выглядеть так: 001*2***101*. Клетки, которые помечены символом «*», содержат бомбы. Обратите внимание, что на корректном поле числа обозначают количество бомб в соседних клетках. Например, поле 2* — некорректное, потому что у клетки с числом 2 должно быть две соседние клетки с бомбой.
Валера хочет создать корректное поле для игры в «Сапер 1D». Он уже нарисовал клетчатую полоску шириной в n клеток, разместил на поле несколько бомб и записал числа в некоторые клетки. Теперь его интересует, сколько существует способов так заполнить оставшиеся клетки бомбами или числами, чтобы получилось корректное поле.
Выходные данные
Выведите одно число — количество способов, которыми Валера может заполнить свободные клетки, получив при этом корректное поле.
Так как ответ может быть очень большим, выведите его по модулю 1000000007 (109 + 7).
Примечание
В первом тестовом примере можно получить следующие корректные поля: 001**1, 001***, 001*2*, 001*10.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
?01???
|
4
|
|
2
|
?
|
2
|
|
3
|
**12
|
0
|
|
4
|
1
|
0
|