Как известно, работа Барни это «PLEASE», и ему в целом нечем заняться на работе, и поэтому он решил сыграть в «чашки и ключ». В этой игре участвуют три одинаковые чашки, выставленные в ряд слева направо. Изначально ключ к сердцу Барни находится под стоящей посередине чашкой.

Затем, за один ход Барни меняет местами чашку посередине с одной из двух других чашек случайным образом (он выберет каждую с одинаковой вероятностью), так что выбранная чашка становится посередине. Игра длится n ходов, и в каждом из них Барни независимо выбирает чашку для обмена со средней на каждом ходу, а ключ всегда остается под чашкой, под которой был в самом начале.

После n-го хода Барни просит девушку указать на чашку, содержащую ключ. Девушка указывает на стоящую посередине чашку, но Барни отвлекся во время игры и не знает, находится ли там ключ или нет. Поэтому Барни просит вас сообщить ему вероятность того, что девушка указала на правильную чашку.

Число ходов n может быть очень большим, поэтому Барни не сообщил вам его. Вместо этого он дал вам массив a₁, a₂, ..., a_k, такой, что

Из-за проблем с точностью Барни просит вас сообщить ответ в виде несократимой дроби. Другими словами, найдите ответ в виде p / q, причем , где  — наибольший общий делитель. Так как p и q могут быть очень большими, достаточно вывести остаток от деления каждого из них на 10⁹ + 7.

Заметьте, что мы хотим, чтобы наибольший общий делитель p и q был равен 1, а не наибольший общий делитель их остатков от деления на 10⁹ + 7.