该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小蓝最近在学习二进制。他想知道 $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$。