TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4398
  • 题目
  • P4398最少得分
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 时间限制1s,空间限制256m
    问题描述

    高一信竞队的期末考试有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