beecrowd | 1353
# Super Poker

**Timelimit: 3**

Por Rujia Liu China

I have a set of super poker cards, consisting of an infinite number of cards. For each positive integer **P**, there are exactly four cards whose value is **P**: Spade(**S**), Heart(**H**), Club(**C**) and Diamond(**D**). There are no cards of other values.

Given two positive integers **N** and **K**, how many ways can you pick up at most **K** cards whose values sum to **N**? For example, if **N** = 15 and **K** = 3, one way is 3**H** + 4**S** + 8**H**, shown below:

There will be at most 20 test cases, each with two integers **N** and **K** (1 ≤ **N** ≤ 10^{9}, 1 ≤ **K** ≤ 10). The input is terminated by **N** = **K** = 0.

For each test case, print the number of ways, modulo 1,000,000,009.

Sample Input | Sample Output |

2 1 |
4 |