## 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 seperated 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

Sample 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: | 0.25s |

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 |