TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P4398
  • 問題
  • P4398最少得分
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 时间限制1s,空间限制256m
    問題説明

    NK信竞队的欢乐赛有n道题目。每AC一道题,就得一分。
    同时,何老板设定了一个"连A"计数器,每AC一道题,计数器加1,每WA一道题,计数器就清零。一旦计数器的读数为k(连续AC了k道题),当前的总得分就翻倍,然后计数器清零。
    比如,n=10,k=3,某同学做题情况如下:

    现在已知道一个同学AC了m道题目,何老板想知道,他最少能得多少分?请你帮忙算算!

    入力形式

    第一行,三个整数n,m,k

    出力形式

    一个整数,表示计算结果。结果可能很大,mod 1000000009 再输出。

    サンプル入力 1

    5 3 2

    サンプル出力 1

    3

    サンプル入力 2

    11 9 3

    サンプル出力 2

    12

    サンプル入力 3

    300 282 7

    サンプル出力 3

    234881124

    ヒント

    \(2 ≤ k ≤ n ≤ 10^9\)
    \(0 ≤ m ≤ n\)


    ソース  改编自codeforces 337C