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.
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 9).
Each test case contains two integers n and k(1≤n,k≤10 9).
Output
Output the required answer modulo 10
9+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;
}
}