CF662A.Gambling Nim

As you know, the game of "Nim" is played with n piles of stones, where the i-th pile initially contains a__i stones. Two players alternate the turns. During a turn a player picks any non-empty pile and removes any positive number of stones from it. The one who is not able to make a move loses the game.

Petya and Vasya are tired of playing Nim, so they invented their own version of the game and named it the "Gambling Nim". They have n two-sided cards, one side of the i-th card has number a__i written on it, while the other side has number b__i. At the beginning of the game the players put all the cards on the table, each card only one of its sides up, and this side is chosen independently and uniformly. Thus they obtain a sequence _c_1, _c_2, ..., c__n, where c__i is equal to a__i or b__i. Then they take n piles of stones, with i-th pile containing exactly c__i stones and play Nim. Petya takes the first turn.

Given that both players play optimally, find the probability of Petya's victory. Output the answer as an irreducible fraction.

众所周知，“Nim”游戏由 $n$ 堆石子组成，其中第 $i$ 堆初始包含 $a_i$ 颗石子。两名玩家轮流进行操作：在每次操作中，一名玩家任选一个非空石子堆，并从中移除任意正整数颗石子；无法进行操作的玩家判负。

佩特亚（Petya）和瓦夏（Vasya）玩腻了标准的 Nim 游戏，于是发明了一种新版本，并将其命名为“赌博 Nim”（Gambling Nim）。他们有 $n$ 张双面卡片，第 $i$ 张卡片的一面写有数字 $a_i$，另一面写有数字 $b_i$。游戏开始时，双方将所有卡片置于桌面上，每张卡片仅有一面朝上，且每张卡片朝上的那一面是独立、均匀随机选择的。这样便得到一个序列 $c_1, c_2, ..., c_n$，其中每个 $c_i$ 等于 $a_i$ 或 $b_i$。接着，他们准备 $n$ 堆石子，使得第 $i$ 堆恰好包含 $c_i$ 颗石子，并以此局面进行标准 Nim 游戏。佩特亚先手。

假设双方均以最优策略进行游戏，求佩特亚获胜的概率。请以最简分数形式输出答案。

The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of cards in the deck.

Each of the following n lines contains the description of one card, consisting of two integers a__i and b__i (0 ≤ a__i, b__i ≤ 1018).

输入的第一行包含一个整数 $n$（$1 \leq n \leq 500\,000$）—— 表示牌组中的卡片数量。

接下来的 $n$ 行每行描述一张卡片，包含两个整数 $a_i$ 和 $b_i$（$0 \leq a_i, b_i \leq 10^{18}$）。

Output the answer as an irreducible fraction p / q. If the probability of Petya's victory is 0, print 0/1.

以最简分数 p / q 的形式输出答案。如果 Petya 获胜的概率为 0，则输出 0/1。