source_code: import java.io.*;
  import java.math.BigInteger;
  import java.util.*;
  
  public class Main {
  
      public static void main(String[] args) throws Exception {
          InputReader in = new InputReader(System.in);
          int n = in.readInt();
          int m = in.readInt();
          int k = in.readInt();
          long wrong = n - m;
          long c = wrong * (k) + k - 1;
          long xk = n - c;
          if (xk <= 0)
              System.out.println((n - wrong) % 1000000009);
          else {
              long x = (long) Math.ceil(xk / (k * 1.0));
              long power = Long.parseLong((BigInteger.valueOf(2).modPow(
                      BigInteger.valueOf(x + 1), BigInteger.valueOf(1000000009))
                      .subtract(BigInteger.valueOf(2))) + "");
              power += 1000000009;
              power %= 1000000009;
              long first = (power * k) % 1000000009;
              // System.out.println(first);
              first += (n - x * k - wrong);
              System.out.println(first % 1000000009);
          }
      }
  
      static class InputReader {
          private InputStream stream;
          private byte[] buf = new byte[1000];
          private int curChar, numChars;
  
          public InputReader(InputStream stream) {
              this.stream = stream;
          }
  
          private 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 int readInt() {
              int c = read();
              while (isSpaceChar(c))
                  c = read();
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              int res = 0;
              do {
                  if (c < '0' || c > '9')
                      throw new InputMismatchException();
                  res *= 10;
                  res += c - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public long readLong() {
              int c = read();
              while (isSpaceChar(c))
                  c = read();
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              long res = 0;
              do {
                  if (c < '0' || c > '9')
                      throw new InputMismatchException();
                  res *= 10;
                  res += c - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public String readString() {
              int c = read();
              while (isSpaceChar(c))
                  c = read();
              StringBuffer res = new StringBuffer();
              do {
                  res.appendCodePoint(c);
                  c = read();
              } while (!isSpaceChar(c));
              return res.toString();
          }
  
          private boolean isSpaceChar(int c) {
              return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
          }
  
          private String readLine0() {
              StringBuffer buf = new StringBuffer();
              int c = read();
              while (c != '\n' && c != -1) {
                  buf.appendCodePoint(c);
                  c = read();
              }
              return buf.toString();
          }
  
          public String readLine() {
              String s = readLine0();
              while (s.trim().length() == 0)
                  s = readLine0();
              return s;
          }
  
          public String readLine(boolean ignoreEmptyLines) {
              if (ignoreEmptyLines)
                  return readLine();
              else
                  return readLine0();
          }
  
          public char readCharacter() {
              int c = read();
              while (isSpaceChar(c))
                  c = read();
              return (char) c;
          }
  
          public double readDouble() {
              int c = read();
              while (isSpaceChar(c))
                  c = read();
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              double res = 0;
              while (!isSpaceChar(c) && c != '.') {
                  if (c == 'e' || c == 'E')
                      return res * Math.pow(10, readInt());
                  if (c < '0' || c > '9')
                      throw new InputMismatchException();
                  res *= 10;
                  res += c - '0';
                  c = read();
              }
              if (c == '.') {
                  c = read();
                  double m = 1;
                  while (!isSpaceChar(c)) {
                      if (c == 'e' || c == 'E')
                          return res * Math.pow(10, readInt());
                      if (c < '0' || c > '9')
                          throw new InputMismatchException();
                      m /= 10;
                      res += (c - '0') * m;
                      c = read();
                  }
              }
              return res * sgn;
          }
      }
  }
  