F. Соня и информатика
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Девочка по имени Соня учится в научном лицее Королевства Кремляндия. Учитель информатики (любимого предмета Сони!) придумал для неё задачу.

Даётся массив $$$a$$$ длины $$$n$$$, состоящий только из чисел $$$0$$$ и $$$1$$$, а также число $$$k$$$. Ровно $$$k$$$ раз происходит следующее:

  • Равновероятно выбираются два числа $$$i$$$ и $$$j$$$ такие, что ($$$1 \leq i < j \leq n$$$).
  • Числа, стоящие на позициях $$$i$$$ и $$$j$$$, меняются местами.

Задача Сони найти вероятность того, что после выполнения всех операций массив $$$a$$$ будет отсортирован по неубыванию. За помощью она обратилась к вам. Помогите Соне решить эту задачу.

Можно показать, что искомая вероятность или равна $$$0$$$, или её можно представить как $$$\dfrac{P}{Q}$$$, где $$$P$$$ и $$$Q$$$ — взаимно простые числа и $$$Q \not\equiv 0~\pmod {10^9+7}$$$.

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

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 100, 1 \leq k \leq 10^9$$$) — длина массива $$$a$$$ и количество операций.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$) — описание массива $$$a$$$.

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

Если искомая вероятность равна $$$0$$$, выведите $$$0$$$, иначе выведите величину $$$P \cdot Q^{-1}$$$ $$$\pmod {10^9+7}$$$, где $$$P$$$ и $$$Q$$$ определены выше.

Примеры
Входные данные
3 2
0 1 0
Выходные данные
333333336
Входные данные
5 1
1 1 1 0 0
Выходные данные
0
Входные данные
6 4
1 0 0 1 1 0
Выходные данные
968493834
Примечание

В первом примере все возможные варианты конечного массива $$$a$$$, после применения ровно двух операций: $$$(0, 1, 0)$$$, $$$(0, 0, 1)$$$, $$$(1, 0, 0)$$$, $$$(1, 0, 0)$$$, $$$(0, 1, 0)$$$, $$$(0, 0, 1)$$$, $$$(0, 0, 1)$$$, $$$(1, 0, 0)$$$, $$$(0, 1, 0)$$$. Следовательно ответ равен $$$\dfrac{3}{9}=\dfrac{1}{3}$$$.

Во втором примере массив не станет отсортированным по неубыванию после одной операции, следовательно ответ равен $$$0$$$.