# 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