如您所知,“Nim”游戏是用 n 堆石子进行的,其中第 i 堆最初包含 ai 石子。两名玩家轮流轮流。在一个回合中,玩家拾取任何非空堆并从中移除任意正数的石子。无法采取行动的人就输掉了比赛。
Petya 和 Vasya 厌倦了玩 Nim,因此他们发明了自己的游戏版本,并将其命名为“Gambling Nim”。他们有n张双面卡片,第i张卡片的一面写着数字ai,而另一面写着数字bi。游戏开始时,玩家将所有牌放在桌上,每张牌只有一面朝上,并且这一面是独立且统一选择的。因此,他们获得了序列 c1, c2, ..., cn,其中 ci 等于 ai 或 bi。然后他们拿 n 堆棋子,其中第 i 堆恰好包含 ci 棋子,然后玩 Nim。佩蒂亚(Petya)先行。
鉴于两名玩家都发挥最佳,求 Petya 获胜的概率。将答案输出为不可约分数。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 500 000) — 这副牌中的牌数。
以下n行每行包含一张卡的描述,由两个整数ai和bi组成(0≤ai,bi≤1018)。
输出
将答案输出为不可约分数 p / q。如果 Petya 获胜的概率为 0,则打印 0/1。
示例
输入 #1
2 1 1 1 1
输出 #1
0/1
输入 #2
2 1 2 1 2
输出 #2
1/2
输入 #3
3 0 4 1 5 2 3
输出 #3
1/1