Oh no, XOR again?

Another XOR problem came up again, and it is as tedious as ever!

You are given integers $N$, $K$, $A$, and $B$. Among the integers from $A$ to $B$ inclusive, count how many of them, when XORed with $N$, have exactly $K$ ones in their binary representation.

The first line contains $N$, $K$, $A$, and $B$, in that order, separated by spaces.

Print the answer.

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

Bitwise XOR is an operation that can be applied to two non-negative integers. For non-negative integers $A$ and $B$, write each in binary, then for each bit position put 0 if the two bits are equal and 1 if they differ. The result is $A \oplus B$.

For example, take $A=10$ and $B=6$. In binary, they are $1010_2$ and $0110_2$. The first and second bits from the right are equal, so they become 0. The third and fourth bits differ, so they become 1. Therefore $A \oplus B$ is $1100_2 = 12$.