题目描述

小蓝最近在学习二进制。他想知道 $1$ 到 $N$ 中有多少个数满足其二进制表示中恰好有 $K$ 个 $1$。你能帮助他吗？

输入描述

输入一行包含两个整数 $N$ 和 $K$。

输出描述

输出一个整数表示答案。

7 2

3

评测用例规模与约定

对于 30% 的评测用例，$1 ≤ N ≤ 10^6, 1 ≤ K ≤ 10$。

对于 60% 的评测用例，$1 ≤ N ≤ 2 × 10^9, 1 ≤ K ≤ 30$。

对于所有评测用例，$1 ≤ N ≤ 10^{18}, 1 ≤ K ≤ 50$。