問題文

正整数 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 としてありうるものの個数を求めてください。

制約

• 1 \leq N \leq 2\times 10^5
• 1 \le M \le 30
• 0 \le A_i < 2^M
• 入力は全て整数

入力例 1

3 3
4 3 6

出力例 1

2

操作後の 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 となります。

入力例 2

5 1
1 1 1 1 1

出力例 2

1

入力例 3

8 4
3 5 14 0 10 3 6 12

出力例 3

4