Time Limit : sec, Memory Limit : KB
Japanese

Zero AND Subsets

非負整数の多重集合a_1,a_2,..,a_Nが与えられます。

この集合の空でない部分集合であって、値のbitwiseANDが0になるものはいくつありますか。

答えを10^9+7で割った余りを求めてください。

入力

N
a_1 a_2...a_N

出力

答えを10^9+7で割った余りを出力せよ。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq a_i \leq 2^{20}-1

入力例

6
8 6 9 1 2 1

出力例

51