Partition

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1049 Accepted Submission(s): 427

Problem Description

Define f(n) as the number of ways to perform n in format of the sum of some positive integers. For instance, when n=4, we have

4=1+1+1+1

4=1+1+2

4=1+2+1

4=2+1+1

4=1+3

4=2+2

4=3+1

4=4

totally 8 ways. Actually, we will have f(n)=2

^(n-1) after observations.

Given a pair of integers n and k, your task is to figure out how many times that the integer k occurs in such 2

^(n-1) ways. In the example above, number 1 occurs for 12 times, while number 4 only occurs once.

 

Input

The first line contains a single integer T(1≤T≤10000), indicating the number of test cases.

Each test case contains two integers n and k(1≤n,k≤10

⁹).

 

Output

Output the required answer modulo 10

⁹+7 for each test case, one per line.

 

Sample Input

2 4 2 5 5

 

Sample Output

5 1

 

 

import java.io.BufferedInputStream;import java.util.*;public class Main {	public static long t1=1000000000+7;	public static void main(String[] args) {		Scanner sc = new Scanner(new BufferedInputStream(System.in));		int t = sc.nextInt();		for (int i = 0; i < t; i++) {			int n = sc.nextInt();			int k = sc.nextInt();			if (k > n) {				System.out.println("0");			} else {				int b = n - k + 1;				if (b == 1)					System.out.println("1");				else if (b == 2)					System.out.println("2");				else if (b == 3)					System.out.println("5");				else {					long num = (power(2,b-1)%t1  + (b - 2) * power(2,b-3))%t1 ;					num%=t1;					System.out.println(num);				}			}		}	}	 public static long power(int a,int n)  	{  	    if (n==0) return 1;  	    if (n==1) return a;  	     long z=power(a,n/a);  	    if (n%2==0)  	        return z*z%t1;  	    else return z*z*a%t1;  	}  }