아 또 XOR이야?

툭하면 나와서 지루하기 짝이 없는 XOR 문제가 또 나와버렸다!

정수 $N$, $K$, $A$, $B$가 주어진다. $A$ 이상 $B$ 이하의 정수 중에서 $N$과 Bitwise XOR 연산을 수행한 결과의 이진수 표기에 $1$이 정확히 $K$개 등장하는 수의 개수를 세어보자.

첫 번째 줄에 $N$, $K$, $A$, $B$가 이 순서대로 공백을 사이에 두고 주어진다.

정답을 출력한다.

• $1 \le N \le 2^{60}$
• $0 \le K \le 60$
• $1 \le A \le B \le 2^{60}$

Bitwise XOR은 두 음이 아닌 정수에 대해 수행할 수 있는 연산이다. 음이 아닌 정수 $A$와 $B$를 이진수로 나타낸 다음, 각 비트별로 같으면 0, 다르면 1을 대응하는 비트에 쓴다. 이렇게 얻은 수가 $A \oplus B$이다.

예를 들어 $A=10$, $B=6$을 보자. 이진수로 $1010_2$와 $0110_2$이다. 오른쪽에서 첫 번째와 두 번째 비트는 같으므로 0이 되고, 세 번째와 네 번째 비트는 다르므로 1이 된다. 따라서 $A \oplus B$는 $1100_2 = 12$이다.