30710번 - 몰래 교환하기

문제

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

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

그러나 아무 카드나 골라 교환하면 기현이에게 들킬 수 있기 때문에, 기현이가 눈치채지 못하게 카드를 교환해야 한다.

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

다시 말해, 카드 $X$에 적힌 정수를 $A,ドル 카드 $Y$에 적힌 정수를 $B$라고 하자. $\left\vert (A\oplus B) -(A+B) \right\vert\leq K$를 만족한다면 두 카드 $X,ドル $Y$를 들키지 않고 몰래 교환할 수 있다. 여기서 $\oplus$는 Bitwise 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$로 나눈 나머지를 출력한다.

제한

힌트