E. Коробки и шары
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В ряд расставлены $$$n$$$ коробок. Коробки пронумерованы от $$$1$$$ до $$$n$$$. В некоторых коробках лежит по одному шару, остальные пустые. Хотя бы в одной коробке есть шар и хотя бы одна коробка пустая.

За один ход вы обязаны выбрать коробку с шаром и соседнюю с ней пустую коробку и переложить шар из одной коробки в другую. Коробки $$$i$$$ и $$$i+1$$$ для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$ считаются соседними друг с другом. Коробки $$$1$$$ и $$$n$$$ не соседние.

Сколько различных расположений шаров может быть после совершения ровно $$$k$$$ ходов? Два расположения называются различными, если есть хотя бы одна такая коробка, что в одном из них в ней есть шар, а в другом нет.

Так как ответ может быть достаточно большой, выведите его остаток от деления на $$$10^9+7$$$.

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

В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 1500$$$; $$$1 \le k \le 1500$$$) — количество коробок и количество ходов.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$a_i \in \{0, 1\}$$$) — $$$0$$$ обозначает пустую коробку, $$$1$$$ обозначает коробку с шаром. В последовательности есть хотя бы один $$$0$$$ и хотя бы одна $$$1$$$.

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

Выведите одно целое число — количество возможных различных расположений шаров после совершения ровно $$$k$$$ ходов, по модулю $$$10^9+7$$$.

Примеры
Входные данные
4 1
1 0 1 0
Выходные данные
3
Входные данные
4 2
1 0 1 0
Выходные данные
2
Входные данные
10 6
1 0 0 1 0 0 0 1 1 1
Выходные данные
69
Примечание

В первом примере есть следующие возможные расположения:

  • 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 — получается из любого из первых двух расположений после первого хода.