AT_code_thanks_festival_2017_f Limited Xor Subset

[problemUrl]: https://atcoder.jp/contests/code-thanks-festival-2017/tasks/code_thanks_festival_2017_f $ N $ 個の正の整数が与えられ、$ i(1≦i≦N) $ 番目の正の整数は $ a_i $ です。 $ N $ 個の整数のうち $ 0 $ 個以上を選んで、選んだ全ての整数のビットごとの排他的論理和を計算します。 計算結果が $ K $ となるような整数の選び方の個数を $ 10^9+7 $ で割った余りを求めてください。 ただし、$ 0 $ 個選んだときのビットごとの排他的論理和は $ 0 $ とします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ a_1 $ $ : $ $ a_N $

条件を満たす整数の選び方の個数を $ 10^9+7 $ で割った余りを出力せよ。

### 制約 - $ 1≦N≦10^5 $ - $ 0≦K≦10^5 $ - $ 1≦a_i\ (1≦i≦N) $ - $ a_1\ +\ …\ +\ a_N≦10^5 $ - 入力は全て整数である。 ### Sample Explanation 1 選んだ全ての整数についてビットごとの排他的論理和が $ K\ =\ 3 $ となるような選び方は以下の $ 4 $ 通りです。 - $ \{a_1,a_2\} $ - $ \{a_1,a_4\} $ - $ \{a_2,a_3\} $ - $ \{a_3,a_4\} $ ### Sample Explanation 2 選んだ全ての整数についてビットごとの排他的論理和が $ K\ =\ 0 $ となるような選び方は以下の $ 8 $ 通りです。 - $ \{\} $ (選んだ整数が $ 0 $ 個の場合) - $ \{a_1,a_2\} $ - $ \{a_1,a_3\} $ - $ \{a_1,a_4\} $ - $ \{a_2,a_3\} $ - $ \{a_2,a_4\} $ - $ \{a_3,a_4\} $ - $ \{a_1,a_2,a_3,a_4\} $