Power of Fibonacci

Time Limit: 5 Seconds

Memory Limit: 65536 KB

Description

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 Fn of Fibonacci numbers is defined by the recurrence relation Fn = Fn - 1 + Fn - 2 with seed values F1 = 1 and F2 = 1.

And your task is to find ΣFiK, the sum of the K-th 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.

Input

There 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 <= 1018, 1 <= K <= 100000).

Output

For each test case, output the remainder of the answer divided by 1000000009.

Sample Input

5
10 1
4 20
20 2
9999 99
987654321987654321 98765


Sample Output

143
487832952
74049690
113297124
108672406


Hint

The first test case, 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 = 143.

The second test case, 120 + 120 + 220 + 320 =3487832979, and 3487832979 = 3 * 1000000009 + 487832952, so the output is 487832952.

None