Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
132 - The 14th Zhejiang University Programming Contest - H
Power of Fibonacci

Time Limit: 5 Seconds      Memory Limit: 65536 KB

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
```

```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.

Submit    Status