Задачи
Сумма произведений
Сумма произведений
Даны натуральные числа \textbf{a}, \textbf{b}, \textbf{n}. Требуется вычислить следующую сумму произведений
\textbf{a·}(\textbf{a+1})\textbf{·}...\textbf{·}(\textbf{a+n-1})\textbf{+}(\textbf{a+1})\textbf{·}(\textbf{a+2})\textbf{·}...\textbf{·}(\textbf{a+n})\textbf{+}...\textbf{+b·}(\textbf{b+1})\textbf{·}...\textbf{·}(\textbf{b+n-1})\textbf{.}
Так как ответ может быть ОЧЕНЬ большим, то вам необходимо определить остаток от деления этого числа на \textbf{1000000009}.
\InputFile
В единственной строке входного файла заданы натуральные числа \textbf{a},\textbf{b},\textbf{n} (\textbf{a} ≤ \textbf{b} ≤ \textbf{10^18}, \textbf{b}-\textbf{a} ≤ \textbf{10^7} и \textbf{n} ≤ \textbf{10^7}).
\OutputFile
В выходной файл выведите искомую сумму произведений по модулю \textbf{1000000009}.
Входные данные #1
1 4 3
Выходные данные #1
210