给出n个连续的题目，已知小明答对了m题。求小明所获得的最低分数是多少？
计分 规则：当答对一题的时候总分加一，同时计分器的分数加一。当答错时，
计分器清零，且总分不改变。但连续答对k题时，也就是计分器分数达到k分时，选手的总分加倍。
当然，是先将第k题的一分加上去后，总分才加倍， 同时计分器清零。
答案对1e9+9取余。
输入描述:
每行三个整数 n, m 和 k (2 ≤ k ≤ n ≤ 1e9; 0 ≤ m ≤ n).
输入不唯一
输出描述:
每行一个整数，代表最低分数。
示例1
说明
显然，错误的题目是第6题的时候，分数变化为 1->4->5->12->13->13
备注:
注意，令mod = 1e9 + 9， 这时（mod * 2 + 3）%mod 小于(mod + 4) % mod, 但是答案要取（mod + 4）% mod.
也就是说我们要找的是最低的总分，而不是取模后的值最小。