Problem Description

Xiaolan has been learning binary recently. He wants to know how many numbers from $1$ to $N$ have exactly $K$ 1s in their binary representation. Can you help him?

Input Format

Input one line containing two integers $N$ and $K$.

Output Format

Output one integer representing the answer.

7 2

3

Hint

For $30\%$ of the testdata, $1 \leq N \leq 10^{6}, 1 \leq K \leq 10$.

For $60\%$ of the testdata, $1 \leq N \leq 2 \times 10^{9}, 1 \leq K \leq 30$.

For all testdata, $1 \leq N \leq 10^{18}, 1 \leq K \leq 50$.

Lanqiao Cup 2021 National Contest, Group B Problem H (Group C Problem J).

Translated by ChatGPT 5