
132  The 14th Zhejiang University Programming Contest  H
In mathematics, Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers of the following integer sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ... By definition, the first two numbers in the Fibonacci sequence are 1 and 1, and each subsequent number is the sum of the previous two. In mathematical terms, the sequence F_{n} of Fibonacci numbers is defined by the recurrence relation F_{n} = F_{n  1} + F_{n  2} with seed values F_{1} = 1 and F_{2} = 1. And your task is to find ΣF_{i}^{K}, the sum of the Kth power of the first N terms in the Fibonacci sequence. Because the answer can be very large, you should output the remainder of the answer divided by 1000000009. InputThere are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case: There are two integers N and K (0 <= N <= 10^{18}, 1 <= K <= 100000). OutputFor each test case, output the remainder of the answer divided by 1000000009. Sample Input5 10 1 4 20 20 2 9999 99 987654321987654321 98765 Sample Output143 487832952 74049690 113297124 108672406 HintThe first test case, 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143. The second test case, 1^{20} + 1^{20} + 2^{20} + 3^{20} =3487832979, and 3487832979 = 3 * 1000000009 + 487832952, so the output is 487832952. 