cf-373 C Quiz

タイトルのソース:http://codeforces.com/problemset/problem/337/C
n，m，kをあげます。
全部でnの問題がありますが、mの問題に答えられます。  あなたが連続してk道に答えたら、点数が倍になります。
あなたが得ることができる最小の点数を求めます。
欲が深い  倍の点数をできるだけ前に置く。
それから数学で計算しました。 

#include 
#include 
#include 
#include 
#include 
#define MOD 1000000009
using namespace std;
#define MAX 1000000
long long n,m,k;
long long exp_mod(long long a,long long n)  //   
{
    long long t;
    if(n==0) return 1%MOD;
    if(n==1) return a%MOD;
    t=exp_mod(a,n/2);
    t=t*t%MOD;
    if((n&1)==1) t=t*a%MOD;
    return t;
}
int main()
{
    while(~scanf("%I64d%I64d%I64d",&n,&m,&k))
    {
        if((n-m)*k>n)
            printf("%I64d
",m);
        else
        {
            long long x=n-(n-m)*k;  //     
            long long y=x/k;        //             
            long long sum=(exp_mod(2,y+1)-2+MOD)%MOD;  //sum   k;
            sum=(sum*k)%MOD;
            sum=(sum+x%k)%MOD;  //    
            sum=(sum+(n-m)*k-(n-m))%MOD;  //         
            printf("%I64d
",sum);
        }
    }
}