G - Guided by XOR

Time limit: 3 s
Memory limit: 1024 MiB
Languages: C, C++, Java, Python, ... (details)

You are given an array $A$ of $n$ integers and an integer $k$. You will start on the first position and you can only move to the right. Formally if you are in the position $i$ you can go to all the positions $j$ such that ($i < j \le n$ and $A_i \oplus A_j < k$), where $\oplus$ denote the xor operation (exclusive or).


Count how many different ways there are to get to the $n$-th position. Two ways are different if there exists at least one position that you visit in one way and not in the other. As the answer can be very large output it modulo $10^9+7$.

Input

First line of the input contains two integers $n, k$ $(1 \le n \le 2 \cdot 10^5,0 \le k \le 2^{20})$.

Second line of the input contains $n$ integers $a_1, a_2,\cdots, a_n$ $(0 \le a_i \le 2^{20})$, where $a_i$ is the value of the $i$-th position of the array.

Output

Print one integer, the numbers of ways to get to the $n$-th position modulo $10^9+7$.

Sample test(s)

Input
3 4 1 3 3
Output
2
Input
4 4 4 3 4 1
Output
0
Input
8 4 2 3 5 6 3 1 4 1
Output
8