1, 2, 3 Addition 7

Interview

Time limit0.25sMemory limit512 MB

Summary

Count ordered compositions of n into exactly m parts, where each part is 1, 2, or 3, modulo 1,000,000,009.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

There are 7 ways to express the integer 4 as a sum of 1, 2, and 3. A sum must use at least one number.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

Given integers n and m, write a program that finds the number of ways to express n as a sum of 1, 2, and 3. The number of terms used must be exactly m.

Input

The first line gives the number of test cases T. Each test case occupies one line and contains the integers n and m. n is a positive integer less than or equal to 1,000. m is also a positive integer less than or equal to n.

Output

For each test case, print the number of ways to express n as a sum of 1, 2, and 3, modulo 1,000,000,009. The number of terms used must be exactly m.

Examples2

Example 1
Input
```
3
4 2
7 5
10 6
```
Expected output
```
3
15
90
```
Example 2
Input
```
4
4 1
4 2
4 3
4 4
```
Expected output
```
0
3
3
1
```