CF337C Quiz

Manao 正在参加一个知识问答竞赛。竞赛包含 $n$ 个连续的问题。每答对一题，玩家会获得 1 分。同时，游戏有一个连续答对题数的计数器。每当玩家答对一题时，这个计数器会加 1。如果玩家答错一题，计数器会被重置为 0。如果在某次答题后，计数器中的数达到了 $k$，那么计数器会被重置，且玩家的分数会翻倍。注意，在这种情况下，先加 1 分，再将总分翻倍。比赛开始时，玩家的分数和连续答对题数计数器均为 0。 Manao 记得他一共答对了 $m$ 题，但他记不清这些题目的顺序。现在他想知道，他的分数最少可能是多少。请你帮助他计算，这个最小分数对 $1000000009$ ($10^9+9$) 取余的结果。

输入包含一行，包含三个用空格分隔的整数 $n$、$m$ 和 $k$（$2 \leq k \leq n \leq 10^9; 0 \leq m \leq n$）。

输出一个整数，表示 Manao 在满足条件时可能获得的最小分数对 $1000000009$ ($10^9+9$) 取余的结果。

样例 1：Manao 在 5 道题中答对了 3 道，每连续答对 2 道题时分数会翻倍。如果 Manao 答对了第 1、3、5 题，他最多只能得到 3 分。 样例 2：现在 Manao 答对了 4 道题。得分最小的情况是只有第 4 题答错。 还需注意，题目要求的是最小的分数本身，而不是其对模数 $1000000009$ 取余得到的最小值。例如，如果 Manao 可以得到 $2000000000$ 或 $2000000020$ 分，答案应为 $2000000000 \bmod 1000000009$，尽管 $2000000020 \bmod 1000000009$ 的结果更小。 由 ChatGPT 5 翻译