В ряд выстроено n лампочек. Лампочки пронумерованы от 1 до n слева направо. Изначально некоторые лампочки включены. Шаасс хочет включить все лампочки. За один ход он может включить лампочку (которая на тот момент должна быть выключенной), если у нее есть хотя бы одна соседняя включенная лампочка.
Юноша знает изначальное состояние лампочек и ему интересно, сколько есть различных способов включить все лампочки. Пожалуйста, посчитайте искомое количество способов по модулю 1000000007 (109 + 7).
Выходные данные
В единственной строке выведите количество различных возможных способов включить все лампочки по модулю 1000000007 (109 + 7).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
1
|
1
|
|
2
|
4 2
1 4
|
2
|
|
3
|
11 2
4 8
|
6720
|