Let $bit(x)$ denote the number of ones in the binary representation of a non-negative integer $x$.

A subarray of an array is called $k$-good if it consists only of numbers with no more than $k$ ones in their binary representation, i.e., a subarray $(l, r)$ of array $a$ is good if for any $i$ such that $l \le i \le r$ condition $bit(a_{i}) \le k$ is satisfied.

You are given an array $a$ of length $n$, consisting of consecutive non-negative integers starting from $0$, i.e., $a_{i} = i$ for $0 \le i \le n - 1$ (in $0$-based indexing). You need to count the number of $k$-good subarrays in this array.

As the answer can be very large, output it modulo $10^{9} + 7$.

Input

Each test consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases. The following lines describe the test cases.

The single line of each test case contains two integers $n$, $k$ ($1 \le n \le 10^{18}, 1 \le k \le 60$).

Output

For each test case, output a single integer — the number of $k$-good subarrays modulo $10^{9} + 7$.

Note

For the first test case $a = [0, 1, 2, 3, 4, 5]$, $k = 1$.

To find the answer, let's write all the numbers in binary representation:

$$a = [\color{green}{000}, \color{green}{001}, \color{green}{010}, \color{red}{011}, \color{green}{100}, \color{red}{101}]$$

From this, it can be seen that the numbers $3$ and $5$ have $2 \ge (k = 1)$ ones in their binary representation, so the answer should include all subarrays that do not contain either $3$ or $5$, which are the subarrays (in $0$-based indexing): ($0$, $0$), ($0$, $1$), ($0$, $2$), ($1$, $1$), ($1$, $2$), ($2$, $2$), ($4$, $4$).