题目详情 - 考试成绩 - 南阳理工学院OJ

ID: 805

远端评测题

1000ms

128MiB

难度: (无)

上传者:

PIAOYI参加了一个考试，有n道题目，初始得分为0，每当答对一道加一分，当连续答对第k道题目时，得分再加一后翻倍，然后k清零。

现在已知他答对了m道题，但是不记得答题正误的顺序，请你帮助他算一下他的最低得分是多少？

Input

多组测试数据，每组测试数据依次输入 n，m，k。
2 <= k <= n <= 1e9 ; 0 < =m < =n
结果可能很大请mod（1e9+9）；

Output

输出最低得分，每组数据占一行

Sample Input

5 3 2
5 4 2

Sample Output

3
6

HINT

</p>

Source