Как известно, работа Барни это «PLEASE», и ему в целом нечем заняться на работе, и поэтому он решил сыграть в «чашки и ключ». В этой игре участвуют три одинаковые чашки, выставленные в ряд слева направо. Изначально ключ к сердцу Барни находится под стоящей посередине чашкой.
Затем, за один ход Барни меняет местами чашку посередине с одной из двух других чашек случайным образом (он выберет каждую с одинаковой вероятностью), так что выбранная чашка становится посередине. Игра длится n ходов, и в каждом из них Барни независимо выбирает чашку для обмена со средней на каждом ходу, а ключ всегда остается под чашкой, под которой был в самом начале.
После n-го хода Барни просит девушку указать на чашку, содержащую ключ. Девушка указывает на стоящую посередине чашку, но Барни отвлекся во время игры и не знает, находится ли там ключ или нет. Поэтому Барни просит вас сообщить ему вероятность того, что девушка указала на правильную чашку.
Число ходов n может быть очень большим, поэтому Барни не сообщил вам его. Вместо этого он дал вам массив a1, a2, ..., ak, такой, что
другими словами,
n равно произведению чисел данного массива.
Из-за проблем с точностью Барни просит вас сообщить ответ в виде несократимой дроби. Другими словами, найдите ответ в виде p / q, причем 
, где 
— наибольший общий делитель. Так как p и q могут быть очень большими, достаточно вывести остаток от деления каждого из них на 109 + 7.
Заметьте, что мы хотим, чтобы наибольший общий делитель p и q был равен 1, а не наибольший общий делитель их остатков от деления на 109 + 7.