問題文

長さ $N$ の非負整数列 $A$ が与えられます。$A$ に対して以下の操作を $0$ 回以上繰り返すことで得られる数列は何種類ありますか？

• 隣接した $2$ 要素を削除し、それらの排他的論理和で置き換える。この操作は $A$ の長さが $2$ 以上である時にのみ行える。

答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを求めてください。

入力

\(N\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)

• $1\leq N\leq 2\times 10^5$
• $0\leq A_i\lt 2^{30}$
• 入力は全て整数

出力

種類数を $10^9+7$ で割った余りを $1$ 行に出力してください。

サンプル

3
1 3 2

4

4
1 4 4 2

7

10
8 2 0 9 1 3 2 4 9 10

360