Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
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$.