comeback.cpp

/*                 When Panda is Life !
                              _,add8ba,
                            ,d888888888b,
                           d8888888888888b                        _,ad8ba,_
                          d888888888888888)                     ,d888888888b,
                          I8888888888888888 _________          ,8888888888888b
                __________`Y88888888888888P"""""""""""baaa,__ ,888888888888888,
            ,adP"""""""""""9888888888P""^                 ^""Y8888888888888888I
         ,a8"^           ,d888P"888P^                           ^"Y8888888888P'
       ,a8^            ,d8888'                                     ^Y8888888P'
      a88'           ,d8888P'                                        I88P"^
    ,d88'           d88888P'                                          "b,
   ,d88'           d888888'                                            `b,
  ,d88'           d888888I                                              `b,
  d88I           ,8888888'            ___                                `b,
 ,888'           d8888888          ,d88888b,              ____            `b,
 d888           ,8888888I         d88888888b,           ,d8888b,           `b
,8888           I8888888I        d8888888888I          ,88888888b           8,
I8888           88888888b       d88888888888'          8888888888b          8I
d8886           888888888       Y888888888P'           Y8888888888,        ,8b
88888b          I88888888b      `Y8888888^             `Y888888888I        d88,
Y88888b         `888888888b,      `""""^                `Y8888888P'       d888I
`888888b         88888888888b,                           `Y8888P^        d88888
 Y888888b       ,8888888888888ba,_          _______        `""^        ,d888888
 I8888888b,    ,888888888888888888ba,_     d88888888b               ,ad8888888I
 `888888888b,  I8888888888888888888888b,    ^"Y888P"^      ____.,ad88888888888I
  88888888888b,`888888888888888888888888b,     ""      ad888888888888888888888'
  8888888888888698888888888888888888888888b_,ad88ba,_,d88888888888888888888888
  88888888888888888888888888888888888888888b,`"""^ d8888888888888888888888888I
  8888888888888888888888888888888888888888888baaad888888888888888888888888888'
  Y8888888888888888888888888888888888888888888888888888888888888888888888888P
  I888888888888888888888888888888888888888888888P^  ^Y8888888888888888888888'
  `Y88888888888888888P88888888888888888888888888'     ^88888888888888888888I
   `Y8888888888888888 `8888888888888888888888888       8888888888888888888P'
    `Y888888888888888  `888888888888888888888888,     ,888888888888888888P'
     `Y88888888888888b  `88888888888888888888888I     I888888888888888888'
       "Y8888888888888b  `8888888888888888888888I     I88888888888888888'
         "Y88888888888P   `888888888888888888888b     d8888888888888888'
            ^""""""""^     `Y88888888888888888888,    888888888888888P'
                             "8888888888888888888b,   Y888888888888P^
                              `Y888888888888888888b   `Y8888888P"^
                                "Y8888888888888888P     `""""^
                                  `"YY88888888888P'
                                       ^""""""""'
*/

using namespace std ;
#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = a; i <= b; i++)
#define FOR(i, n) for (int i = 0; i < n; i++)
#define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define PI 3.1415926535897932385
#define uint64 unsigned long long
#define Int long long
#define int64 long long
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define ff first
#define ss second
#define bit(n) (1<<(n))
#define Last(i) ( (i) & (-i) )
#define sq(x) ((x) * (x))
#define mp make_pair
Int R , B , K ;
const Int MAXN = 1e3 + 50 ;
Int dp[ MAXN ][ 8*MAXN  ] ;
Int pre[ MAXN ][ 8*MAXN  ] ;
const Int  M = 1e9 + 9;
/*Int dp2[ 300 ][ 300 ][ 300 ] ;
Int rec( Int ball , Int rem , Int cons )
  {
    if( cons == K + 1 or rem < 0 )return 0 ;
    if( ball == B )
     {
       if( rem == 0 )return 1 ;
       return 0 ;
     }
    if( dp2[ball][rem][cons] != -1 )return  dp2[ball][rem][cons]%M ;

    Int sum = 0  ;
    sum = (sum + rec( ball + 1 , rem , cons + 1 ) )%M ;
    for( Int i = 1 ; i <= 6 ; i ++ )
       sum = (sum + rec(ball+1,rem-i,0))%M ;

    dp2[ball][rem][cons] = sum%M ;
    return sum ;
  }
*/

int main ( )
 {

   //FOR( i , 300 )FOR( j , 300 )FOR(k , 300 )dp2[i][j][k]  = -1 ;

   scanf("%lld%lld%lld",&R,&B,&K) ;

  // Int ans = rec( 0 , R , 0 ) ;
  // cout<<ans<<endl;
  dp[0][0] = 1 ; // dp[i][j] number of ways to score j runs on i balls ;
  pre[0][0] =  1 ;

  for( Int i = 1 ; i <= B ; i ++ ) // number of balls go from 1 to B
    {
      for( Int j = 1 ; j <= 6 ; j ++ ) // number of ways
        for( Int sum = 0 ; sum <= R ; sum ++  ) // number of runs score
             if( sum >= j ) dp[i][sum] = ( dp[i][sum] + dp[i-1][sum-j] ) %M ;

        for( Int sum = 0 ; sum <= R ;sum ++ )
              pre[i][sum] = ( pre[i-1][sum ] + dp[i][sum] ) % M ;

       for( Int sum = 0 ; sum <= R ; sum ++  )
           dp[i][sum] =  (dp[i][sum] + pre[i-1][sum] )%M  ;

       if( i >= ( K + 1 ) )
       for( Int sum = 0 ; sum <= R ; sum ++  )
            {  dp[i][sum] =  ( dp[i][sum] - pre[i-(K+1)][sum] )%M ; }


      // for( Int sum = 0 ; sum  <= R; sum ++ )
        //  cout<<i<<" "<<sum<<" "<< dp[i][sum]<<endl;


      // cout<<i<<" "<<sum<<" "<<dp[i][sum]<<endl;

     }

       cout<<(dp[B][R]%M + M)%M<<endl;

 }