No.183 たのしい排他的論理和(EASY)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 275
作問者 : 紙ぺーぱー紙ぺーぱー
9 ProblemId : 470 / 出題時の順位表

問題文

kamipeipaa君は頭が悪いので勉強を始めました。今kamipeipaa君が解いている問題は以下のような問題です。

$N$個のスイッチを発見した。$i$番目のスイッチには$A_i$という整数が書かれている。あなたは$i$番目のスイッチを押すことで、ある整数$X$に対して
$X = X \oplus A_i$
という操作を行うことができる。ただし$\oplus$とはビットXORの記号である(参考)。
一度押したスイッチは二度と使用することはできない。
$X$ははじめ$0$である。
あなたが作ることができる整数は何種類あるか。

kamipeipaa君と一緒にあなたも解いてあげてください。

入力

$N$
$A_1$ $A_2$ ... $A_N$

1行目にスイッチの数$N(1 \le N \le 5000)$が与えられる。
2行目にスイッチに書かれた整数$A_i(1 \le A_i \le 16384(2^{14}))$が空白区切りで与えられる。

出力

作ることができる整数の総数を1行で出力しなさい。改行を忘れないこと。

サンプル

サンプル1
入力
2
1 2 
出力
4

$0 = 0$
$1 = 0 \oplus 1$
$2 = 0 \oplus 2$
$3 = 0 \oplus 1 \oplus 2$
の4種類の値を作ることができます。

サンプル2
入力
6
1 1 4 5 1 4
出力
4

6つ整数が与えられても4種類しか作れない場合もあります。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。