Сумма произведений
Простая
Ограничение по времени выполнения 3 секунды
Ограничение по использованию памяти 64 мегабайта
Даны натуральные числа a, b, n. Требуется вычислить следующую сумму произведений
a·(a+1)·...·(a+n-1)+(a+1)·(a+2)·...·(a+n)+...+b·(b+1)·...·(b+n-1).
Так как ответ может быть ОЧЕНЬ большим, то вам необходимо определить остаток от деления этого числа на 1000000009.
Входные данные
В единственной строке входного файла заданы натуральные числа a,b,n (a ≤ b ≤ 10^18, b-a ≤ 10^7 и n ≤ 10^7).
Выходные данные
В выходной файл выведите искомую сумму произведений по модулю 1000000009.
Примеры
Ввод #1
Ответ #1
Отправки 85
Коэффициент принятия 21 %