Кратко напомним правила игры Ним. Имеется n кучек камней, при этом в кучке i изначально лежит a_i камней. Два игрока по очереди выбирают непустую кучку и берут из неё произвольное положительное количество камней. Проигрывает тот, кто не может сделать ход.

Петя и Вася давно устали от обычного Нима, поэтому придумали свою версию игры и назвали её «Азартный Ним». У них есть n двусторонних карточек, на одной стороне i-й карточки написано число a_i, а на другой b_i. Перед началом игры карты выкладываются на стол, при этом каждая карта независимо от других равновероятно кладётся одной из двух сторон вверх. Получается некоторая последовательность c₁, c₂, ..., c_n, где c_i равно a_i или b_i. После этого Петя и Вася делают n кучек камней (при этом в кучке номер i лежит c_i камней) и играют в Ним. Петя ходит первым.

Известно, что и Петя и Вася играют в Ним оптимально. Найдите вероятность победы Пети. Ответ выведите как несократимую дробь.