В ряд расставлены \(n\) коробок. Коробки пронумерованы от \(1\) до \(n\). В некоторых коробках лежит по одному шару, остальные пустые. Хотя бы в одной коробке есть шар и хотя бы одна коробка пустая.
За один ход вы обязаны выбрать коробку с шаром и соседнюю с ней пустую коробку и переложить шар из одной коробки в другую. Коробки \(i\) и \(i+1\) для всех \(i\) от \(1\) до \(n-1\) считаются соседними друг с другом. Коробки \(1\) и \(n\) не соседние.
Сколько различных расположений шаров может быть после совершения ровно \(k\) ходов? Два расположения называются различными, если есть хотя бы одна такая коробка, что в одном из них в ней есть шар, а в другом нет.
Так как ответ может быть достаточно большой, выведите его остаток от деления на \(10^9+7\).
Выходные данные
Выведите одно целое число — количество возможных различных расположений шаров после совершения ровно \(k\) ходов, по модулю \(10^9+7\).
Примечание
В первом примере есть следующие возможные расположения:
- 0 1 1 0 — получается после перемещения шара из коробки \(1\) в коробку \(2\);
- 1 0 0 1 — получается после перемещения шара из коробки \(3\) в коробку \(4\);
- 1 1 0 0 — получается после перемещения шара из коробки \(3\) в коробку \(2\).
Во втором примере есть следующие возможные расположения:
- 1 0 1 0 — три способа получить ее: просто верните обратно шар после первой операции;
- 0 1 0 1 — получается из любого из первых двух расположений после первого хода.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1
1 0 1 0
|
3
|
|
2
|
4 2
1 0 1 0
|
2
|
|
3
|
10 6
1 0 0 1 0 0 0 1 1 1
|
69
|