27378번 - 아 또 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$에 대해, $A$와 $B$를 이진수로 나타낸 다음 각 비트별로 서로 같으면 $0$, 다르면 $1$을 대응하는 비트로 한 것이 XOR의 결과인 $A \oplus B$가 된다. 예를 들어 $A=10$, $B=6$을 생각해 보자. $A$와 $B$는 각각 이진수로 표현하면 $1010_2$와 $0110_2$이다. 작은 쪽에서부터 첫 번째와 두 번째 비트는 서로 같기 때문에 $0$, 세 번째와 네 번째 비트는 서로 다르기 때문에 $1$이 되어 $A \oplus B$는 $1100_2 = 12$가 된다.