Misha and Permutation

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Misha is an expert on combinatorics, so he knows a lot about permutations. Recently, he learned the definition of a convex polygon and invented too many new problems involving permutations. Please help him solve one of them.
Let's define a function on a set a with size k: F(a_{1}, a_{2}, ... , a_{k}). Imagine that we have sticks of lengths a_{1}, a_{2}, ... , a_{k}. F(a_{1}, a_{2}, ... , a_{k}) = 1, if and only if a convex polygon can be created from these sticks. F(a_{1}, a_{2}, ... , a_{k}) = 0, otherwise.
Misha has the identity permutation over n elements — I_{n} (I_{n} = {1, 2, 3, .. n}). He wants to know the sum of the function F over all possible distinct ksized subsets of I_{n}.
Please help Misha find this sum. Since its value may be very large, you should output the sum modulo 10^{9}+7.
Input
The first line of input contains an integer T denoting the number of test cases. Each of the next T lines contains two spaceseparated integers — n and k.Output
For each test case, output a single line containing a single integer — the solution of Misha's problem modulo 10^{9}+7.Constraints
 1 ≤ T ≤ 500
 3 ≤ k ≤ 7
 1 ≤ k ≤ n ≤ 10^{9}
Subtasks
 Subtask 1: (10 pts) Sum of n over all test cases not be greater than 15.
 Subtask 2: (20 pts) Sum of n over all test cases not be greater than 1000.
 Subtask 3: (30 pts) 1 ≤ n ≤ 10^{6}
 Subtask 4: (40 pts) 1 ≤ n ≤ 10^{9}
Example
Input: 5 3 3 6 4 777 5 777777 7 1000000000 6 Output: 0 14 367816 989165211 930411765
Explanation:
Example case 1. There is only one subset: {1, 2, 3}. Since, F(1, 2, 3) = 0, the answer is 0.
Example case 2. There are C(6, 4) = 15 possible subsets. F(1, 2, 3, 6) = 0, and the value of F on all other subsets equals 1. Therefore, the answer is 15  1 = 14.
Author:  mgch 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/MGCHPERM 
Tags  convexpolygon, dec15, hard, interpolation, mgch, polynomial, precomputation, recurrences 
Date Added:  3102015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 