TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4398
  • Problem
  • P4398最少得分
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 时间限制1s,空间限制256m
    Description

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

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

    Input Format

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

    Output Format

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

    Sample Input 1

    5 3 2

    Sample Output 1

    3

    Sample Input 2

    11 9 3

    Sample Output 2

    12

    Sample Input 3

    300 282 7

    Sample Output 3

    234881124

    Hint

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


    Source  改编自codeforces 337C