- Описание
- Отправленные решения
355. Карточная игра
В нерабочее время сотрудники Яндекс часто собираются, чтобы поиграть в настольные игры. В одну из таких встреч настал черёд следующей карточной игры для двух человек.
Игра происходит некоторой колодой карт, которая состоит из карт $N$ различных типов. Количество карт разных типов может быть различно. Перед началом игры карты перемешиваются (все перестановки карт равновероятны) и раздаются поровну между игроками (одному игроку чётные карты, а другому нечётные). Гарантируется, что число карт чётно. Затем каждый игрок считает, сколько у него есть уникальных карт. Тот игрок, у которого уникальных карт больше, побеждает.
В день перед этой встречей колода карт попала к вам в руки, и вам захотелось посчитать, с какой вероятностью во время игры случится ничья.
Формат ввода
В первой строке задаётся целое число $N$ ($1 \leq N \leq 50$). Во второй строке — $N$ чисел $a_i$, определяющих количество карт каждого из типов ($1 \leq a_i \leq 10$).
Формат вывода
Гарантируется, что искомая вероятность представляется в виде несократимой рациональной дроби $\frac{P}{Q}$, где $P$ — целое число, а $Q$ — натуральное число, не делящееся на $10^9+7$.
Выведите остаток от деления числа $P \cdot Q^{-1}$ на $10^9+7$, где $X^{-1}$ обозначает обратный к $X$ элемент в кольце вычетов по модулю $10^9+7$, то есть такое целое число $Y$, что $0 \leq Y \lt 10^9+7$ и остаток от деления числа $X \cdot Y$ на $10^9+7$ равен 1.
Можно показать, что $X^{-1}$ существует и единственно для любого целого числа $X$, не делящегося на $10^9+7$.
Примечание
В первом тесте есть единственный вариант раздачи: каждый игрок получает по карте первого типа. Значит, ничья происходит с вероятностью 1.
Во втором тесте аналогично: все перестановки карт в колоде приводят к тому, что один игрок получает карту первого типа, а другой — карту второго типа, значит, ничья происходит с вероятностью 1.
В третьем тесте все перестановки карт в колоде приводят к тому, что один игрок получает одну карту первого типа и одну карту второго типа, а второй игрок получает 2 карты второго типа, то есть ничья невозможна.
В четвёртом тесте все перестановки карт в колоде приводят к нескольким исходам:
- 122 - 333 (один игрок получает все карты третьего типа, а другой — все остальные), случается с вероятностью $\frac{1}{10}$ и не приводит к ничьей
- 123 - 233 (один игрок получает по карте каждого типа, а другой — все остальные), случается с вероятностью $\frac{3}{5}$ и не приводит к ничьей
- 133 - 223 (один игрок получает одну карту третьего типа и все карты второго типа, а другой — все остальные), случается с вероятностью $\frac{3}{10}$ и приводит к ничьей
Получаем, что в данном тесте ничья случается с вероятностью $\frac{3}{10}$.
Ограничения
Ограничение времени
2 с
Ограничение памяти
512 МБ
Пример 1
1
2
1
Пример 2
2
1 1
1
Пример 3
2
1 3
0
Пример 4
3
1 2 3
100000001