몰래 교환하기

기현이는 양의 정수가 하나씩 적힌 카드 $N$장을 가지고 있다. 기현이는 카드 $N$장을 보기 좋게 탁자에 일렬로 늘어놓았다.

주원이는 카드 배열이 마음에 들지 않아 기현이 몰래 배열을 바꾸려고 한다. 주원이는 탁자에 놓인 카드 중 두 장을 골라 교환하는 과정을 반복해서 원하는 순서로 카드를 재배열하려고 한다.

하지만 아무 카드나 골라 교환하면 기현이에게 들킬 수 있다. 그래서 주원이는 기현이가 눈치채지 못하게 카드를 교환해야 한다.

기현이는 두 카드의 정수를 배타적 논리합(Bitwise XOR)한 결과와 두 카드 정수의 합의 차이가 $K$ 이하면 교환을 눈치채지 못한다.

즉, 카드 $X$에 적힌 정수를 $A$, 카드 $Y$에 적힌 정수를 $B$라고 하자. $\left\vert (A\oplus B) -(A+B) \right\vert\leq K$를 만족하면 두 카드 $X$, $Y$를 들키지 않고 몰래 교환할 수 있다. 여기서 $\oplus$는 비트 단위 XOR 연산자이고, $K$는 교환 전에 미리 정해진 상수이다.

초기 카드 배열이 주어졌을 때, 가능한 최종 배열의 가짓수를 구해보자.

첫 번째 줄에 카드의 수 $N$과 숫자 $K$가 공백으로 구분되어 정수로 주어진다. ($1\leq N\leq 100\,000$; $0\leq K<2^{19}$)

두 번째 줄에는 탁자에 놓인 카드의 초기 배열 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다. ($0\leq a_i<2^{18}$; $1\leq i\leq N$)

첫 번째 줄에 가능한 최종 배열의 가짓수를 $10^9+7$로 나눈 나머지를 출력한다.