Adding 1, 2, 3 (9)

Interview

Time limit1sMemory limit512 MB

Summary
Count ordered compositions of n into parts 1, 2, and 3 that use at most m terms, and output each count modulo 1,000,000,009.
Level

Medium5 of 10

Topics
Dynamic programming, Combinatorics, Math, Prefix sum
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 at most 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 no greater than 1,000. m is also a positive integer no greater than 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 at most m.

Examples4

  1. Example 1

    Input
    3
4 2
7 5
10 6
    Expected output
    3
37
151

  2. Example 2

    Input
    4
4 1
4 2
4 3
4 4
    Expected output
    0
3
6
7

  3. Example 3

    Input
    7
7 1
7 2
7 3
7 4
7 5
7 6
7 7
    Expected output
    0
0
6
22
37
43
44

  4. Example 4

    Input
    10
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
    Expected output
    0
0
0
10
61
151
228
264
273
274