Manao is taking part in a quiz. The quiz consists of n consecutive questions. A correct answer gives one point to the player. The game also has a counter of consecutive correct answers. When the player answers a question correctly, the number on this counter increases by 1. If the player answers a question incorrectly, the counter is reset, that is, the number on it reduces to 0. If after an answer the counter reaches the number k, then it is reset, and the player's score is doubled. Note that in this case, first 1 point is added to the player's score, and then the total score is doubled. At the beginning of the game, both the player's score and the counter of consecutive correct answers are set to zero.

Manao remembers that he has answered exactly m questions correctly. But he does not remember the order in which the questions came. He's trying to figure out what his minimum score may be. Help him and compute the remainder of the corresponding number after division by 1000000009 (10^9 + 9).


-----Input-----

The single line contains three space-separated integers n, m and k (2 ≤ k ≤ n ≤ 10^9; 0 ≤ m ≤ n).


-----Output-----

Print a single integer — the remainder from division of Manao's minimum possible score in the quiz by 1000000009 (10^9 + 9).


-----Examples-----
Input
5 3 2

Output
3

Input
5 4 2

Output
6



-----Note-----

Sample 1. Manao answered 3 questions out of 5, and his score would double for each two consecutive correct answers. If Manao had answered the first, third and fifth questions, he would have scored as much as 3 points.

Sample 2. Now Manao answered 4 questions. The minimum possible score is obtained when the only wrong answer is to the question 4.

Also note that you are asked to minimize the score and not the remainder of the score modulo 1000000009. For example, if Manao could obtain either 2000000000 or 2000000020 points, the answer is 2000000000 mod 1000000009, even though 2000000020 mod 1000000009 is a smaller number.

Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms

Number theory

Mathematics

Matrices
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
(n, m, k) = map(int, input().split())
MOD = 1000000009
x = m - (n // k * (k - 1) + n % k)
if x <= 0:
	print(m % MOD)
	return
print((m - x + (pow(2, x + 1, MOD) + 2 * MOD - 2) * k - x * (k - 1)) % MOD)


from collections import defaultdict
mod = int(1000000009)

def is_good(n, a, b):
	while n:
		digit = n % 10
		if digit != a and digit != b:
			return False
		n = n // 10
	return True
(n, m, k) = map(int, input().split())
m -= n % k
score = n % k
n -= n % k
sets = n // k
used = sets * (k - 1)
if used >= m:
	print(m + score)
	exit()
else:
	filled = m - used
	score += 2 * k * (2 ** filled % mod - 1) % mod
	score += int(sets - filled) * (k - 1) % mod
print(score % mod)


p = int(1000000000.0 + 9)

def f2(l):
	(n, m, k) = l
	w = n - m
	cc = n - w * k
	if cc < k:
		return m
	nkp1 = cc // k + 1
	f = w * (k - 1) + cc % k - (k << 1)
	return f + (k << nkp1) % p

def f(l):
	(n, m, k) = l
	w = n - m
	cc = n - w * k
	if cc < k:
		return m
	g = ((2 << cc // k) - 2) % p
	fcc = k * g + cc % k
	return fcc + w * (k - 1)
l = list(map(int, input().split()))
print(f2(l) % p)


from sys import stdin
mod = 1000000009

def find(k, ak):
	return (pow(2, ak + 1, mod) - 2 + mod) % mod * k % mod
(n, m, k) = map(int, stdin.readline().split())
w = min(n // k, n - m)
ak = n // k - w
print((find(k, ak) + m - k * ak) % mod)


MOD = 1000000009
(n, m, k) = map(int, input().split())
x = max(0, m - (n - n % k) // k * (k - 1) - n % k)
res = (pow(2, x + 1, MOD) - 2) % MOD * k % MOD
z = (m - x * k) % MOD
res = (res + z) % MOD
print(res)


MOD = 1000000009
(n, m, k) = [int(x) for x in input().split()]
num0 = n - m
num1fin = num0 * (k - 1)
if num1fin >= m:
	print(m)
else:
	num1open = m - num1fin
	sets = num1open // k
	rem = num1open % k
	print(((pow(2, sets, MOD) - 1) * 2 * k + rem + num1fin) % MOD)


import sys
from math import gcd, sqrt, ceil, log2
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right
import math
sys.setrecursionlimit(2 * 10 ** 5 + 10)
import heapq
from itertools import permutations
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_sum(bit, i):
	s = 0
	i += 1
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def update(bit, n, i, v):
	i += 1
	while i <= n:
		bit[i] += v
		i += i & -i

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def primeFactors(n):
	sa = set()
	sa.add(n)
	while n % 2 == 0:
		sa.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			sa.add(i)
			n = n // i
	return sa

def seive(n):
	pri = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if pri[p] == True:
			for i in range(p * p, n + 1, p):
				pri[i] = False
		p += 1
	return pri

def check_prim(n):
	if n < 0:
		return False
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def getZarr(string, z):
	n = len(string)
	(l, r, k) = (0, 0, 0)
	for i in range(1, n):
		if i > r:
			(l, r) = (i, i)
			while r < n and string[r - l] == string[r]:
				r += 1
			z[i] = r - l
			r -= 1
		else:
			k = i - l
			if z[k] < r - i + 1:
				z[i] = z[k]
			else:
				l = i
				while r < n and string[r - l] == string[r]:
					r += 1
				z[i] = r - l
				r -= 1

def search(text, pattern):
	concat = pattern + '$' + text
	l = len(concat)
	z = [0] * l
	getZarr(concat, z)
	ha = []
	for i in range(l):
		if z[i] == len(pattern):
			ha.append(i - len(pattern) - 1)
	return ha

def mergeIntervals(arr):
	arr.sort(key=lambda x: x[0])
	m = []
	s = -10000
	max = -100000
	for i in range(len(arr)):
		a = arr[i]
		if a[0] > max:
			if i != 0:
				m.append([s, max])
			max = a[1]
			s = a[0]
		elif a[1] >= max:
			max = a[1]
	if max != -100000 and [s, max] not in m:
		m.append([s, max])
	return m

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def sol(n):
	seti = set()
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			seti.add(n // i)
			seti.add(i)
	return seti
mod = 10 ** 9 + 9
(n, m, k) = map(int, input().split())
x = max(0, m - (n - n % k) // k * (k - 1) - n % k)
z = (pow(2, x + 1, mod) - 2) * k % mod
rem = m - k * x
print((z + rem) % mod)


M = 1000000009
(n, m, k) = map(int, input().split())
x = max(0, m - (n - n % k) // k * (k - 1) - n % k)
print(((pow(2, x + 1, M) - 2) * k + m - x * k) % M)


mod = 10 ** 9 + 9
(n, m, k) = map(int, input().split())
x = int(max(0, m - (n - n % k) / k * (k - 1) - n % k))
p = pow(2, x + 1, mod) - 2
ans = int((p % mod * (k % mod) % mod + (m - x * k + mod) % mod) % mod)
print(ans)


(num, m, k) = list(map(int, input().split()))
na = num - m
if (na + 1) * (k - 1) >= m:
	print(m)
else:
	sa = na * (k - 1)
	nsa = m - sa
	M = 10 ** 9 + 9
	ans = (pow(2, nsa // k + 1, M) - 2) * k
	ans += nsa % k
	ans += sa
	print((ans + 0) % 1000000009)


import os
import sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd, log
from collections import *
from bisect import *
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
g = lambda : input().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
mod = int(1000000000.0 + 9)
(n, m, k) = gil()
ans = min(n % k, m) % mod
m -= min(m, n % k)
n -= n % k
if m:
	l = n // k
	dbl = max(0, m - l * (k - 1))
	if dbl:
		delta = (pow(2, dbl + 1, mod) + mod - 2) % mod
		delta *= k
		delta %= mod
		ans += delta
		ans %= mod
	l -= dbl
	ans += (m - dbl * k) % mod
print(ans % mod)


(n, m, k) = map(int, input().split())
chunks = n // k
freespots = chunks * (k - 1) + n % k
if m <= freespots:
	print(m)
else:
	doubles = m - freespots
	dchunks = doubles
	chunks -= dchunks
	total = (pow(2, dchunks, 1000000009) - 1) * k * 2
	total += n % k + chunks * (k - 1)
	print(total % 1000000009)


(n, m, k) = map(int, input().split())
d = max(0, n // k - (n - m))
M = 1000000009
if d > 0:
	res = (2 * k * (pow(2, d, M) - 1) % M + m - k * d) % M
else:
	res = m
print(res)


d = 1000000009
(n, m, k) = map(int, input().split())
if (n - m) * k > n:
	print(m)
else:
	t = n // k - n + m + 1
	print(((pow(2, t, d) - 1 - t) * k + m) % d)


class Matrix:

	def __init__(self, ar):
		self.ar = ar

	def __mul__(self, other):
		n = len(other.ar)
		m = len(self.ar)
		p = len(other[0])
		ans = [[0] * p for i in range(m)]
		for i in range(m):
			for j in range(p):
				for k in range(n):
					ans[i][j] += self[i][k] * other[k][j]
		return Matrix(ans)

	def __mod__(self, other):
		m = len(self[0])
		for i in range(len(self.ar)):
			for j in range(m):
				self[i][j] %= other
		return self

	def __getitem__(self, key):
		return self.ar[key]
mod = 10 ** 9 + 9

def power(number, n):
	res = number
	while n:
		if n & 1:
			res *= number
			res %= mod
			n -= 1
		number *= number
		number %= mod
		n >>= 1
	return res
(n, m, k) = map(int, input().split())
wrong = n - m
if wrong * k > n:
	print(m)
else:
	n -= wrong * k
	num = n // k
	m1 = Matrix([[0, k, k]])
	m2 = Matrix([[2, 0, 0], [1, 1, 0], [0, 1, 1]])
	if num == 0:
		print(m)
	elif num == 1:
		print((m + k) % mod)
	else:
		print((m + (m1 * power(m2, num - 1))[0][0]) % mod)


import os
import sys
from io import BytesIO, IOBase
import math

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m, k) = map(int, input().split())
p = n // k
mws = (k - 1) * p + n % k
mod = 1000000009
if m <= mws:
	print(m)
else:
	con = m - mws
	acon = k * (pow(2, con + 1, mod) - 2) % mod
	m -= k * con
	ans = (acon + m) % mod
	print(ans)


MOD = 10 ** 9 + 9
dp = {0: 1, 1: 2}

def two_pow(n):
	if n not in dp:
		dp[n] = two_pow(n // 2) * two_pow(n // 2) * (2 if n % 2 == 1 else 1) % MOD
	return dp[n]
(n, m, k) = list(map(int, input().split()))
fit = n - n // k
if m <= fit:
	print(m)
else:
	a = m - fit
	rem = m - k * a
	print(((two_pow(a + 1) - 2) * k + rem) % MOD)


MOD = 1000000009

def p2(e):
	if e == 0:
		return 1
	elif e % 2 == 1:
		return 2 * p2(e - 1) % MOD
	else:
		return p2(e // 2) ** 2 % MOD
(n, m, k) = map(int, input().split())
x = (m - min(n - m, m // (k - 1)) * (k - 1)) // k
print((2 * k * (p2(x) - 1) + m - x * k) % MOD)


(n, m, k) = map(int, input().split())
import math
if m <= math.ceil(n * (k - 1) / k):
	print(m)
	exit(0)
ans = math.ceil(n * (k - 1) / k)
over = m - ans
N = 1000000009

def exponentiation(bas, exp):
	if exp == 0:
		return 1
	if exp == 1:
		return bas % N
	t = exponentiation(bas, int(exp / 2))
	t = t * t % N
	if exp % 2 == 0:
		return t
	else:
		return bas % N * t % N
print((ans + ((exponentiation(2, over + 1) - 2) * k - over * (k - 1))) % N)


(n, m, k) = map(int, input().split())
correct = m
wrong = n - m
taken = wrong * (k - 1)
left = correct - taken
pair = left // k
left = left % k
if taken >= m:
	print(m)
	exit(0)
score = 0
if pair > 0:
	score += (pow(2, pair + 1, 1000000009) - 2) * k
print((taken + left + score) % 1000000009)


(n, m, k) = map(int, input().split())
p = k - 1
MOD = 1000000009
tMatches = n // k * (k - 1) + n % k
if tMatches >= m:
	print(m)
else:
	leftMatches = m - tMatches
	m -= k * leftMatches
	cost = k * 2 * (pow(2, leftMatches, MOD) - 1)
	cost += m
	print(cost % MOD)


global MOD
MOD = int(1000000000.0 + 9)

def pow(m, n):
	ans = 1
	while n:
		if n & 1:
			ans = ans * m % MOD
		m = m * m % MOD
		n >>= 1
	return ans

def getAns(n, m, k):
	numk = n // k
	if numk * (k - 1) >= m:
		return m
	rest_n = n - k * numk
	rest_m = m - numk * (k - 1)
	if rest_m <= rest_n:
		return (numk * (k - 1) + rest_m) % MOD
	t = rest_m - rest_n
	num = rest_n + t * k
	ans = (numk - t) * (k - 1) % MOD
	numk = num // k
	ans = (ans + num - numk * k) % MOD
	ans = ans + 2 * (k * (pow(2, numk) - 1)) % MOD
	return ans % MOD
(n, m, k) = map(int, input().split())
print(getAns(n, m, k))


z = 10 ** 9 + 9
(n, m, k) = map(int, input().split())
i = n - m
x = (n - k + 1) // k
if k * i >= n - k + 1:
	print((n - i) % z)
else:
	l = n - k + 1
	f = l - (i - 1) * k - 1
	t = f // k
	f = t * k
	v = 2 * (pow(2, t, z) - 1) * k + (n - f - i)
	print(v % z)


(n, m, k) = map(int, input().split())
mod = 10 ** 9 + 9
c = m
inc = n - m
rep = n // k
if rep <= inc:
	print(c)
else:
	rem_c = m - (k - 1) * inc
	score = (k - 1) * inc
	rep2 = rem_c // k
	score += (pow(2, rep2 + 1, mod) - 2) * k
	rem_c -= rep2 * k
	score += rem_c
	print(score % mod)


global MOD
MOD = int(1000000000.0 + 9)

def pow(m, n):
	ans = 1
	while n:
		if n & 1:
			ans = ans * m % MOD
		m = m * m % MOD
		n >>= 1
	return ans

def quiz(n, m, k):
	X = n // k
	if X * (k - 1) >= m:
		return m
	rest_n = n - k * X
	rest_m = m - X * (k - 1)
	if rest_m <= rest_n:
		return (X * (k - 1) + rest_m) % MOD
	X = rest_m - rest_n
	return ((pow(2, X + 1) - 2) * k + m - X * k) % MOD
(n, m, k) = map(int, input().split())
print(quiz(n, m, k))


(n, m, k) = map(int, input().split())
if n - m >= n // k:
	print(m)
else:
	longest_correct_streak = n - k * (n - m)
	p = longest_correct_streak // k
	print((k * (pow(2, p + 1, 1000000009) - 2) + longest_correct_streak % k + (n - m) * (k - 1)) % 1000000009)


3

def modulo_power(modulo, power, base):
	if power == 0:
		return 1
	if power == 1:
		return base
	remainder = power % 2
	power -= remainder
	half = modulo_power(modulo, power / 2, base)
	return half * half * modulo_power(modulo, remainder, base) % modulo
data = [int(token) for token in input().split()]
(num_questions, num_correct, doubler) = data
num_wrong = num_questions - num_correct
tail = num_wrong * (doubler - 1)
head = num_correct - tail
if head < 0:
	print(num_correct)
	return
num_doublings = head // doubler
remainder = head - num_doublings * doubler
modulo = 10 ** 9 + 9
result = (2 * doubler * (modulo_power(modulo, num_doublings, 2) - 1) + remainder + tail) % modulo
print(result)


def chk(x):
	d = (m - x) // (k - 1) * k
	if (m - x) % (k - 1):
		d += 1 + (m - x) % (k - 1)
	if d <= n - x:
		return True
	else:
		return False

def calc(e):
	if e == 1:
		return 2
	if e & 1:
		d = 2
	else:
		d = 1
	f = calc(e >> 1)
	d = d * f % D * f % D
	return d
(n, m, k) = list(map(int, input().split()))
D = 1000000009
l = 0
h = n
while l < h:
	mid = l + h >> 1
	if chk(mid):
		h = mid
	else:
		l = mid + 1
h = calc(l // k + 1) - 2
if h < 0:
	h += D
print((k * h % D + m - l // k * k) % D)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase

def main():
	(n, m, k) = [int(x) for x in input().split()]
	mod = 1000000009
	availablePositions = (k - 1) * (n // k) + n % k
	if availablePositions >= m:
		points = m
	else:
		positionsLeft = m - availablePositions
		points = ((pow(2, positionsLeft + 1, mod) - 2) * k % mod + (m - k * positionsLeft) % mod) % mod
	print(points)
BUFFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
input = lambda : sys.stdin.readline().rstrip('\r\n')

def print(*args, **kwargs):
	sep = kwargs.pop('sep', ' ')
	file = kwargs.pop('file', sys.stdout)
	atStart = True
	for x in args:
		if not atStart:
			file.write(sep)
		file.write(str(x))
		atStart = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
main()


MOD = 1000000009

def log_mult(a, p):
	if p == 0:
		return 1
	else:
		z = log_mult(a, p // 2)
		z = z * z % MOD
		if p % 2 == 1:
			return a * z % MOD
		else:
			return z

def log_iterative(a, p):
	res = 1
	while p > 0:
		if p % 2 == 1:
			res = res * a % MOD
		a = a * a % MOD
		p //= 2
	return res
(n, m, k) = list(map(int, input().split()))
c = n // k * (k - 1) + n % k
if c >= m:
	print(m)
else:
	d = m - c
	res = log_iterative(2, d + 1) - 2
	res = res * k % MOD
	print((res + m - d * k) % MOD)


(n, corecte, k) = list(map(int, input().split()))
incorecte = n - corecte
mod = 10 ** 9 + 9
corecte_consecutive = max(0, n - incorecte * k)
dublari = corecte_consecutive // k
corecte_ramase = corecte - corecte_consecutive

def power(b, exp):
	if exp == 0:
		return 1
	half = power(b, exp // 2)
	if exp % 2 == 0:
		return half * half % mod
	return half * half * b % mod
score = (power(2, dublari + 1) - 2) * k + corecte_ramase + corecte_consecutive % k
print(score % mod)


import os, sys
from io import BytesIO, IOBase

def main():
	mod = 10 ** 9 + 9
	(n, m, k) = map(int, input().split())
	(hi, lo, x) = (10 ** 9, 1, 0)
	while hi >= lo:
		mid = (hi + lo) // 2
		if (n - mid - 1) // k * (k - 1) + (n - mid - 1) % k >= m - mid:
			x = mid
			hi = mid - 1
		else:
			lo = mid + 1
	print(((pow(2, x // k + 1, mod) - 2) * k + x % k + m - x) % mod)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, m, k) = map(int, input().split())
(x, c, ic, ans, mod) = (min(m // (k - 1), n - m), m, n - m, 0, 10 ** 9 + 9)
c = c - (k - 1) * x
(p, r) = (c // k, c % k)
ans = ((pow(2, p + 1, mod) - 2 + mod) % mod * (k % mod) % mod + (k - 1) * x + r) % mod
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
import math
from collections import Counter
from bisect import bisect_right
(n, m, k) = map(int, input().split())
skip = n - m
mod = 10 ** 9 + 9
var = n // k
if var <= skip:
	print(m)
else:
	x = var - skip
	ans = (2 ** (1 + x) % mod - 2) * k + m - x * k
	print(ans % mod)


(n, m, k) = map(int, input().split())
if n - n // k >= m:
	exit(print(m))
mod = int(1000000000.0 + 9)
x = n // k + m - n
r = pow(2, x + 1, mod) - 2
a = r * k + m - x * k
print((a % mod + mod) % mod)


from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def powmod(y, m):
	res = 1
	x = 2
	while y > 0:
		if y & 1:
			res = res * x % m
		y >>= 1
		x = x * x % m
	return res

def solve():
	mod = 1000000009
	(n, m, k) = mi()
	x = n // k * (k - 1)
	n -= n // k * k
	x += n
	if m <= x:
		print(m)
	else:
		x1 = m - x
		ans = 0
		x3 = powmod(x1 + 1, mod)
		x3 = (x3 - 2 + mod) % mod
		ans = x3 * k % mod
		ans += m - x1 * k
		ans %= mod
		print(int(ans))
solve()


MOD = 10 ** 9 + 9
(n, m, k) = map(int, input().split())
x = n // k + m - n
if n - n // k < m:
	x = n // k + m - n
	ans = pow(2, x + 1, MOD) - 2
	ans = ans * k + m - x * k
	print(ans % MOD)
else:
	print(m)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 10 ** 9 + 9
EPS = 1e-06

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def bigmod(a, b, c):
	if b == 0:
		return 1
	if b % 2 == 0:
		x = bigmod(a, b / 2, c)
		return x * x % c
	else:
		return a % c * bigmod(a, b - 1, c) % c
(n, m, k) = value()
sections = n // k
minScore = n % k + sections * (k - 1)
covered = max(m - minScore, 0)
score = (bigmod(2, covered, M) - 1 + M) % M
score = score * (2 * k) % M % M
score = (score + (m - covered * k)) % M
print(score)


from math import *
from collections import *
import sys
sys.setrecursionlimit(10 ** 9)
mod = 1000000009

def power(x, y):
	res = 1
	x = x % mod
	while y > 0:
		if y & 1 == 1:
			res = res * x % mod
		y = y >> 1
		x = x * x % mod
	return res
(n, m, k) = map(int, input().split())
s = n // k
ct = (k - 1) * s + n % k
if ct >= m:
	print(m)
else:
	diff = m - ct
	ans = power(2, diff + 1) - 2
	ans *= k
	ans %= mod
	ans += (k - 1) * (s - diff) % mod
	ans %= mod
	ans += n % k
	ans %= mod
	print(ans)


b = 10 ** 9 + 9

def f(q):
	x = q // 1000
	y = q % 1000
	num = 2 ** 1000 % b
	res = 1
	for i in range(x):
		res = res * num % b
	res = res * 2 ** y % b
	return res

def F(n, m, k):
	r = n % k
	if m <= n // k * (k - 1) + r:
		print(m % b)
	else:
		q = m - (n // k * (k - 1) + r)
		print((m + (f(q + 1) - q - 2) * k) % b)
(n, m, k) = [int(x) for x in input().split(' ')]
F(n, m, k)


R = lambda : map(int, input().split())
(n, m, k) = R()
rem = n % k
zeros = n // k
if n - zeros >= m:
	print(m)
else:
	fulls = max(0, m - zeros * (k - 1) - n % k)
	zeros -= fulls
	acc = ((1 << fulls) - 1) % (10 ** 9 + 9) * k * 2
	print((acc + zeros * (k - 1) + rem) % (10 ** 9 + 9) if m else 0)


(n, m, k) = map(int, input().split())
mod = 10 ** 9 + 9
x = n - m
if x >= n // k:
	print(m)
else:
	y = n - k * x
	a = y // k
	b = y % k
	c = pow(2, a, mod)
	if c == 0:
		c = mod - 1
	else:
		c -= 1
	ans = 2 * k % mod * c
	ans %= mod
	ans += x * (k - 1) + b
	ans %= mod
	print(ans)


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def add(a, b):
	return (a + b) % 1000000009

def sub(a, b):
	return (a - b % 1000000009 + 1000000009) % 1000000009

def mul(a, b):
	return a * b % 1000000009

def qpow(a, n):
	k = a
	r = 1
	for i in range(32):
		if n & 1 << i:
			r = mul(r, k)
		k = mul(k, k)
	return r
(n, m, k) = mints()
c = (n + 1) // k
z = c * (k - 1)
if n - c * k >= 0:
	z += n - c * k
d = 0
if z < m:
	d = m - z
else:
	print(m)
	exit(0)
s = mul(k, mul(2, sub(qpow(2, d), 1)))
s = sub(add(s, z), mul(d, k - 1))
print(s)


MOD = 1000000009

def solve(a, n):
	ans = 1
	p = a
	while n > 0:
		if n % 2 == 1:
			ans *= p
		n //= 2
		ans %= MOD
		p = p * p % MOD
	return ans
(n, m, k) = map(int, input().split())
p = n - m + 1
if (k - 1) * p >= m:
	print(m)
else:
	v = m - (p - 1) * (k - 1)
	ans = (p - 1) * (k - 1)
	t = v // k
	ans = (ans + k * (solve(2, t) - 1) * 2 % MOD + MOD + v % k) % MOD
	print(ans)


mod = 1000000009
(n, m, k) = map(int, input().split())
x = n // k * (k - 1) + n % k
if x >= m:
	print(m)
else:
	t = m - x
	u = pow(2, t, mod)
	u = (2 * (u - 1) * k + m - t * k) % mod
	print(u)


(n, m, k) = map(int, input().split())
mod = 1000000000 + 9
x = m - (n // k * (k - 1) + n % k)
if x <= 0:
	print(m % mod)
else:
	print((m - x + (pow(2, x + 1, mod) + 2 * mod - 2) * k - x * (k - 1)) % mod)


import sys
inf = float('inf')
(mod, MOD) = (1000000009, 998244353)

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
(n, m, k) = get_ints()
maxi = n // k * (k - 1) + n % k
if m <= maxi:
	print(m)
	exit()
extra = m - maxi
ans = 0
ans += 2 * k * (pow(2, extra, mod) - 1)
ans += (n // k - extra) * (k - 1)
ans += n % k
ans %= mod
print(ans)


from math import ceil
(n, m, p) = map(int, input().split())
mod = 10 ** 9 + 9
z = n // p * (p - 1) + n % p
if m <= z:
	print(m % mod)
else:
	x = m - z
	z = z - x * (p - 1)
	an = 2 * p * (pow(2, x, mod) - 1) + z
	print(an % mod)


(n, m, k) = map(int, input().split())
pri = pow(10, 9) + 9
x = n % k
y = n // k
if m <= y * (k - 1) + x:
	print(m)
	exit()
else:
	sert = n - m
	left = m - sert * (k - 1)
	g = m - left
	sets = left // k
	le = left % k
	total = k * (pow(2, sets + 1, pri) - 2)
	total %= pri
	print((total + g + le) % pri)


MOD = 1000000009
(n, m, k) = list(map(int, input().split()))
x = m - (n // k * (k - 1) + n % k)
if x <= 0:
	print(m)
else:
	print((m - x + (pow(2, x + 1, MOD) - 2) * k - x * (k - 1)) % MOD)