Codeforces Round 362 (Div. 1) |
---|
Закончено |
Как известно, работа Барни это «PLEASE», и ему в целом нечем заняться на работе, и поэтому он решил сыграть в «чашки и ключ». В этой игре участвуют три одинаковые чашки, выставленные в ряд слева направо. Изначально ключ к сердцу Барни находится под стоящей посередине чашкой.
Затем, за один ход Барни меняет местами чашку посередине с одной из двух других чашек случайным образом (он выберет каждую с одинаковой вероятностью), так что выбранная чашка становится посередине. Игра длится n ходов, и в каждом из них Барни независимо выбирает чашку для обмена со средней на каждом ходу, а ключ всегда остается под чашкой, под которой был в самом начале.
После n-го хода Барни просит девушку указать на чашку, содержащую ключ. Девушка указывает на стоящую посередине чашку, но Барни отвлекся во время игры и не знает, находится ли там ключ или нет. Поэтому Барни просит вас сообщить ему вероятность того, что девушка указала на правильную чашку.
Число ходов n может быть очень большим, поэтому Барни не сообщил вам его. Вместо этого он дал вам массив a1, a2, ..., ak, такой, что
Из-за проблем с точностью Барни просит вас сообщить ответ в виде несократимой дроби. Другими словами, найдите ответ в виде p / q, причем , где — наибольший общий делитель. Так как p и q могут быть очень большими, достаточно вывести остаток от деления каждого из них на 109 + 7.
Заметьте, что мы хотим, чтобы наибольший общий делитель p и q был равен 1, а не наибольший общий делитель их остатков от деления на 109 + 7.
В первой строке содержится единственное целое число k (1 ≤ k ≤ 105) — количество элементов в массиве, данном Барни.
Во второй строке содержатся k целых чисел a1, a2, ..., ak (1 ≤ ai ≤ 1018) — элементы массива.
В единственной строке выведите строку вида x / y, где x — остаток от деления p на 109 + 7, а y — остаток от деления q на 109 + 7.
1
2
1/2
3
1 1 1
0/1
Название |
---|