Super Poker
Por Rujia Liu 
China
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 3H + 4S + 8H, shown below:
There will be at most 20 test cases, each with two integers N and K (1 ≤ N ≤ 109, 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 |