Кратко напомним правила игры Ним. Имеется n кучек камней, при этом в кучке i изначально лежит ai камней. Два игрока по очереди выбирают непустую кучку и берут из неё произвольное положительное количество камней. Проигрывает тот, кто не может сделать ход.
Петя и Вася давно устали от обычного Нима, поэтому придумали свою версию игры и назвали её «Азартный Ним». У них есть n двусторонних карточек, на одной стороне i-й карточки написано число ai, а на другой bi. Перед началом игры карты выкладываются на стол, при этом каждая карта независимо от других равновероятно кладётся одной из двух сторон вверх. Получается некоторая последовательность c1, c2, ..., cn, где ci равно ai или bi. После этого Петя и Вася делают n кучек камней (при этом в кучке номер i лежит ci камней) и играют в Ним. Петя ходит первым.
Известно, что и Петя и Вася играют в Ним оптимально. Найдите вероятность победы Пети. Ответ выведите как несократимую дробь.
В первой строке входных данных записано целое число n (1 ≤ n ≤ 500 000) — количество карт в колоде.
Каждая из последующих n строк содержит описание одной карты, состоящее из двух чисел ai и bi (0 ≤ ai, bi ≤ 1018).
Выведите ответ в виде несократимой дроби p / q. Если вероятность победы Пети равна нулю, то выведите 0/1.
2
1 1
1 1
0/1
2
1 2
1 2
1/2
3
0 4
1 5
2 3
1/1
Название |
---|