На окружности длины $$$L$$$ задана равномерная система координат, координата — это точка из $$$[0, L)$$$. Дано $$$N$$$ точек на окружности, $$$i$$$-я точка имеет координату $$$X_i$$$. Каждая точка равновероятно и независимо окрашивается в красный или синий цвет. Определить вероятность того, что центр круга, ограниченного этой окружностью, будет лежать и в выпуклой оболочке синих точек, и в выпуклой оболочке красных точек.
Первая строка содержит целые числа $$$N$$$ ($$$1 \leq N \leq 10^6$$$) и $$$L$$$ ($$$N \leq L \leq 10^9$$$). Далее записаны $$$N$$$ целых чисел $$$X_1, X_2, \ldots, X_N$$$ ($$$0 \leq X_i \lt L$$$ для $$$0 \leq i \lt N$$$, $$$X_i \neq X_j$$$ для $$$i \neq j$$$) — координаты заданных точек.
Выведите одно целое число $$$R$$$ ($$$0 \leq R \lt 1\,000\,000\,007$$$) — искомую вероятность по модулю $$$1\,000\,000\,007$$$. Гарантируется, что искомую вероятность можно выразить в виде несократимой дроби $$$P/Q$$$. Требуется найти такое число $$$R$$$, что $$$R \cdot Q \equiv P \pmod{1\,000\,000\,007}$$$
4 100 0 30 50 80
125000001
8 100 1 12 34 45 51 84 88 92
515625004
$$$1/8 \mod 1\,000\,000\,007 = 125\,000\,001$$$
$$$25/64 \mod 1\,000\,000\,007 = 515\,625\,004$$$
| 2020-2021 ICPC, Moscow Subregional |
|---|
| Закончено |
