石の山が $N$ 個あり、$i$ 番目の山には石が $A_{i}$ 個あります。

高橋くんと最強の Nim マシン Anstoppable Omnipotent King of Ishitori 、通称 Aoki はこれらの山を使って Nim で対戦します。

Nim とは、以下の操作を交互に繰り返し、操作が行えなくなったほうが負けとなるゲームです。

操作：石が $1$ 個以上残っている山を $1$ つ選び、そこから $1$ 個以上の石を取り除く。

最強の Nim マシン Aoki は自分の番に 最適な 操作の中から一様ランダムに一つを選んで行いますが、整備不良のため、自分の最初の番だけは 可能な 操作の中から一様ランダムに一つを選んで行います。

先攻プレイヤーの情報 $S$ が与えられます。$S$ が Takahashi の場合は高橋くんが先攻、Aoki の場合は最強の Nim マシン Aoki が先攻です。

高橋くんが最適に行動した場合の勝率を求めてください。答えは有理数になることが証明できるので、それを既約分数の形で出力してください。

• $1 \le N \le 2\times 10^{5}$
• $1 \le A_{i} \le 10^{9}$
• $N, A_{i}$ は整数
• $S$ は Takahashi か Aoki のいずれか

この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。

1. ($70$ 点)

• $N \le 2\times 10^{3}$
• $\sum_{i=1}^{N} A_{i} \le 5\times 10^{3}$
• $S$ は Takahashi

2. ($70$ 点)

• $N \le 2\times 10^{3}$
• $\sum_{i=1}^{N} A_{i} \le 5\times 10^{3}$
• $S$ は Aoki

3. ($70$ 点)

• $\sum_{i=1}^{N} A_{i} \le 5\times 10^{5}$
• $S$ は Takahashi

4. ($70$ 点)

• $\sum_{i=1}^{N} A_{i} \le 5\times 10^{5}$
• $S$ は Aoki

5. ($70$ 点)

• $S$ は Takahashi

6. ($70$ 点)

• $S$ は Aoki

7. ($230$ 点)

• 追加の制約はない。

入力は以下の形式で標準入力から与えられる。

答えを既約分数の形で一行に出力せよ。厳密には、答えとなる有理数が既約分数で $P/Q$ と表せるとき、 $P$ 、/、$Q$ をこの順に一行に出力せよ。間に余分な空白などを入れてはならない。