source_code: import java.io.IOException;
  import java.io.OutputStreamWriter;
  import java.io.BufferedWriter;
  import java.util.InputMismatchException;
  import java.io.OutputStream;
  import java.io.PrintWriter;
  import java.io.Writer;
  import java.math.BigInteger;
  import java.io.InputStream;
  
  /**
   * Built using CHelper plug-in
   * Actual solution is at the top
   * @author coderbd
   */
  public class Main {
  	public static void main(String[] args) {
  		InputStream inputStream = System.in;
  		OutputStream outputStream = System.out;
  		InputReader in = new InputReader(inputStream);
  		OutputWriter out = new OutputWriter(outputStream);
  		TaskA solver = new TaskA();
  		solver.solve(1, in, out);
  		out.close();
  	}
  }
  
  class TaskA {
      public static long MOD = 1000000009L;
  
      public long pow(long n, long p) {
          if (p == 0)
              return 1L;
          if (p == 1)
              return n;
          long ret = 1L;
          if (p % 2L != 0)
              ret = n;
          long tmp = pow(n, p / 2L);
          ret = (ret * tmp) % MOD;
          ret = (ret * tmp) % MOD;
          return ret;
      }
  
      public long func(long n, long k) {
          long times = n / k;
          long ret = n - times * k;
          ret += ((pow(2L, times + 1L) + MOD - 2L) % MOD) * k % MOD;
          return ret;
      }
  
      public void solve(int testNumber, InputReader in, OutputWriter out) {
          long n = in.readLong();
          long m = in.readLong();
          long k = in.readLong();
          long wrong = n - m;
          long wow = n / k;
          long ans;
          if (wrong >= wow)
              ans = m;
          else
              ans = (func(n - wrong * k, k) + (k - 1L) * wrong % MOD) % MOD;
  
          out.printLine(ans);
      }
  }
  
  class InputReader {
  
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
  
      public InputReader(InputStream stream) {
          this.stream = stream;
      }
  
      public int read() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = stream.read(buf);
              }
              catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
  
      public long readLong() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = read();
          }
          long res = 0L;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = read();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
  
      public static boolean isSpaceChar(int c) {
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
  
      }
  
  class OutputWriter {
  
      private final PrintWriter writer;
  
      public OutputWriter(OutputStream outputStream) {
          writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
      }
  
      public OutputWriter(Writer writer) {
          this.writer = new PrintWriter(writer);
      }
  
      public void print(Object...objects) {
          for (int i = 0; i < objects.length; i++) {
              if (i != 0)
                  writer.print(' ');
              writer.print(objects[i]);
          }
      }
  
      public void printLine(Object...objects) {
          print(objects);
          writer.println();
      }
  
      public void close() {
          writer.close();
      }
  
      }
  
  