eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сума добутків

Сума добутків

Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB

Задано натуральні числа a, b, n. Потрібно обчислити наступну суму добутків

(a+1)·...·(a+n-1)+(a+1)·(a+2)·...·(a+n)+...+b·(b+1)·...·(b+n-1).

Так як відповідь може бути ДУЖЕ великою, то вам необхідно визначити остачу від ділення цього числа на 1000000009.

Вхідні дані

У єдиному рядку вхідного файлу задані натуральні числа a,b,n (ab10^18, b-a10^7 и n10^7).

Вихідні дані

У вихідний файл виведіть шукану суму добутків по модулю 1000000009.

Приклад

Вхідні дані #1
1 4 3
Вихідні дані #1
210