Pascal Bit Sum

と を () で定義します。

ただし、 は xor である、つまり

です。

長さ の配列 が与えられるので

を について mod で求めてください。

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

答えを 行で出力してください。 行目に のときの計算結果を出力してください。

4
2 1 3 4

2
3
5
10

2
877914575 602436426

877914575
480350994