SP7356 ITERBIT - Iterated Bitcount Function
题目描述
设 $f(x)$ 为 $x$ 的二进制表示中 $1$ 的数量。
定义 $f^k(x)$ 的方法如下：
- 当 $k = 1$ 时，$f^k(x) = f(x)$；
- 当 $k > 1$ 时，$f^k(x) = f^{(k-1)}(f(x))$。
定义 $f^*(x)$ 为最小的满足 $f^k(x) = 1$ 的正整数 $k$。
现在，给定整数 $N$ 和 $K$，需要计算出有多少个整数 $x$ 在 $1$ 到 $N$ 之间且满足 $f^*(x) = K$。
### 输入格式
第一行输入一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行中，每行包含两个以空格分隔的整数 $N$ 和 $K$。
### 输出格式
对于每个测试用例，输出一个整数表示结果，结果需对 $1000000007$ 取模。
### 样例输入
```
6
1 1
2 1
3 1
3 2
13 3
20 2
```
### 样例输出
```
1
2
2
1
3
10
```
### 数据范围与提示
- $1 \leq T \leq 1000$
- $1 \leq N \leq 10^{500}$
- $1 \leq K \leq 10$
**本翻译由 AI 自动生成**
输入格式
无
输出格式
无