• [1111] Super Poker

  • 时间限制: 3000 ms　内存限制: 65535 K
  • 问题描述

  • 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<=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.
  • 样例输入
  • 2 1 
2 2 
2 3 
50 5 
0 0
  • 样例输出
  • 4 
10 
10 
1823966
  • 提示
  • 无
  • 来源
  • The Seventh Hunan Collegiate Programming Contest
  • 操作

显示春菜