- Карточная игра
В нерабочее время сотрудники Яндекс часто собираются, чтобы поиграть в настольные игры. В одну из таких встреч настал черёд следующей карточной игры для двух человек.
Игра происходит некоторой колодой карт, которая состоит из карт N различных типов. Количество карт разных типов может быть различно. Перед началом игры карты перемешиваются (все перестановки карт равновероятны) и раздаются поровну между игроками (одному игроку чётные карты, а другому нечётные). Гарантируется, что число карт чётно. Затем каждый игрок считает, сколько у него есть уникальных карт. Тот игрок, у которого уникальных карт больше, побеждает.
В день перед этой встречей колода карт попала к вам в руки, и вам захотелось посчитать, с какой вероятностью во время игры случится ничья.
Формат ввода
В первой строке задаётся целое число N (1≤N≤50). Во второй строке — N чисел ai, определяющих количество карт каждого из типов (1≤ai≤10).
Формат вывода
Гарантируется, что искомая вероятность представляется в виде несократимой рациональной дроби PQ, где P — целое число, а Q — натуральное число, не делящееся на 109+7.
Выведите остаток от деления числа P⋅Q−1 на 109+7, где X−1 обозначает обратный к X элемент в кольце вычетов по модулю 109+7, то есть такое целое число Y, что 0≤Y<109+7 и остаток от деления числа X⋅Y на 109+7 равен 1.
Можно показать, что X−1 существует и единственно для любого целого числа X, не делящегося на 109+7.
Примечание
В первом тесте есть единственный вариант раздачи: каждый игрок получает по карте первого типа. Значит, ничья происходит с вероятностью 1.
Во втором тесте аналогично: все перестановки карт в колоде приводят к тому, что один игрок получает карту первого типа, а другой — карту второго типа, значит, ничья происходит с вероятностью 1.
В третьем тесте все перестановки карт в колоде приводят к тому, что один игрок получает одну карту первого типа и одну карту второго типа, а второй игрок получает 2 карты второго типа, то есть ничья невозможна.
В четвёртом тесте все перестановки карт в колоде приводят к нескольким исходам:
122 - 333 (один игрок получает все карты третьего типа, а другой — все остальные), случается с вероятностью 110101 и не приводит к ничьей
123 - 233 (один игрок получает по карте каждого типа, а другой — все остальные), случается с вероятностью 3553 и не приводит к ничьей
133 - 223 (один игрок получает одну карту третьего типа и все карты второго типа, а другой — все остальные), случается с вероятностью 310103 и приводит к ничьей
Получаем, что в данном тесте ничья случается с вероятностью 310103.