Manao 正在参加测验。测验由 n 个连续的问题组成。正确的答案会给玩家一分。游戏还设有连续正确答案计数器。当玩家正确回答问题时,该计数器上的数字加1。如果玩家回答错误,则计数器重置,即计数器上的数字减为0。如果回答后计数器达到数字k,则重置,玩家的分数加倍。请注意,在这种情况下,首先将 1 分添加到玩家的分数中,然后将总分数加倍。游戏开始时,玩家的得分和连续正确答案的计数器都设置为零。
Manao 记得他已经正确回答了 m 个问题。但他不记得问题出现的顺序。他试图算出他的最低分数可能是多少。帮助他计算相应数字除以 1000000009 (109 + 9) 后的余数。
输入
单行包含三个空格分隔的整数 n、m 和 k (2 ≤ k ≤ n ≤ 109;0 ≤ m ≤ n)。
输出
打印一个整数 — Manao 在测验中的最低可能分数除以 1000000009 (109 + 9) 所得的余数。
示例
输入 #1
5 3 2
输出 #1
3
输入 #2
5 4 2
输出 #2
6
注意
示例1。Manao 回答了 5 个问题中的 3 个问题,每连续正确回答两个,他的分数就会翻倍。如果马纳奥回答了第一、第三和第五个问题,他将获得多达3分。
示例 2。现在 Manao 回答了 4 个问题。当问题 4 唯一错误答案时,即获得最低可能分数。
另请注意,系统会要求您最小化分数,而不是分数模 1000000009 的余数。例如,如果 Manao 可以获得 2000000000 或 2000000020 分,则答案为 2000000000 mod 1000000009,即使2000000020 mod 1000000009 是一个较小的数字。