AT_pakencamp_2023_day1_k Or Set

正整数 $ M $ と、長さ $ N $ の非負整数列 $ A=(A_1,A_2,\dots ,A_N) $ が与えられます。ここで、 $ 0 \leq A_i \leq 2^M-1 $ が保証されます。また、最初 $ X=0 $ である整数 $ X $ があります。 あなたは、 $ A $ の要素を自由に並べ替えた後、以下の操作を $ i=1,2,\ldots,N $ の順で行います。 - $ X \ \mathrm{or} \ A_i \neq 2^M-1 $ ならば、 $ X $ を $ X \ \mathrm{or} \ A_i $ に置き換える。 操作後の $ X $ としてありうるものの個数を求めてください。 $ \mathrm{or} $ とは 整数 $ a,b $ のビットごとの論理和 $ a \ \mathrm{or} \ b $ は以下のように定義されます。 - $ a \ \mathrm{or} \ b $ を二進表記したときの $ 2^k \ (0 \leq k) $ の位の数は、 $ a,b $ をを二進表記したときの $ 2^k $ の位の数のうち $ 1 $ であるものが存在するのであれば $ 1 $ 、そうでなければ $ 0 $ である。 例えば、 $ 12 \ \mathrm{or} \ 6=14 $ となります。(二進表記すると $ 1100 \ \mathrm{or} \ 0110=1110 $ )

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

答えを出力せよ。

### Sample Explanation 1 操作後の $ X $ として考えられるものは、 $ 3,6 $ の $ 2 $ 通りです。 例えば 、 $ A=(4,3,6) $ の場合、操作は以下のようにして行われます。 - $ X \ \mathrm{or} \ A_1 = 0 \ \mathrm{or} \ 4 = 4 ≠ 2^3-1 $ なので、 $ X $ を $ 4 $ で置き換える。 - $ X \ \mathrm{or} \ A_2 = 4 \ \mathrm{or} \ 3 = 7 = 2^3-1 $ なので、操作を行わない。 - $ X \ \mathrm{or} \ A_3= 4 \ \mathrm{or} \ 6 = 6 ≠ 2^3-1 $ なので、 $ X $ を $ 6 $ で置き換える。 よって、最終的な $ X $ の値は $ 6 $ となります。 ### Constraints - $ 1 \leq N \leq 2\times 10^5 $ - $ 1 \le M \le 30 $ - $ 0 \le A_i < 2^M $ - 入力は全て整数