44. Карточная игра

В нерабочее время сотрудники Яндекс часто собираются, чтобы поиграть в настольные игры. В одну из таких встреч настал черёд следующей карточной игры для двух человек.

Игра происходит некоторой колодой карт, которая состоит из карт $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}$.