ITERBIT - Iterated Bitcount Function
Let f(x) be the number of 1's in the binary representation of x.
We can define f^k(x) as f(x) for k = 1, and f^(k-1)(f(x)) for k > 1.
Let f^*(x) be the smallest k >= 1 such that f^k(x) = 1.
Given N and K, how many numbers x between 1 and N inclusive have f^*(x) = K?
Input
The first line contains the number of test cases T. Each of the next T lines contains two space separated numbers N and K.
Output:
Output one line corresponding to each test case, containing the answer for the corresponding test case. Output all answers modulo 1000000007.
Sample
Input: 6 1 1 2 1 3 1 3 2 13 3 20 2 Output: 1 2 2 1 3 10
Constraints
1 <= T <= 1000
1 <= N <= 10^500
1 <= K <= 10
Added by: | Varun Jalan |
Date: | 2010-09-20 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC VB.NET |
Resource: | own problem, used for Al Khwarizm '10 |