Девочка по имени Соня учится в научном лицее Королевства Кремляндия. Учитель информатики (любимого предмета Сони!) придумал для неё задачу.
Даётся массив \(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}\).
Выходные данные
Если искомая вероятность равна \(0\), выведите \(0\), иначе выведите величину \(P \cdot Q^{-1}\) \(\pmod {10^9+7}\), где \(P\) и \(Q\) определены выше.
Примечание
В первом примере все возможные варианты конечного массива \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
0 1 0
|
333333336
|
|
2
|
5 1
1 1 1 0 0
|
0
|
|
3
|
6 4
1 0 0 1 1 0
|
968493834
|