Çarpımların cəmi

Verilmiş təbii ədədlər a, b, n. Aşağıdakı hasil cəmini hesablamalısınız:

[ a $\cdot$ (a+1) $\cdot$ ...$\cdot$ (a+n-1) + (a+1) $\cdot$ (a+2) $\cdot$ ...$\cdot$ (a+n) + ...+ b $\cdot$ (b+1) $\cdot$ ...$\cdot$ (b+n-1) ]

Cavab çox böyük ola biləcəyi üçün, bu ədədin 1000000009-a bölünməsindən qalanı tapmalısınız.

Giriş verilənləri

Giriş faylının yeganə sətrində təbii ədədlər a, b, n (a ≤ b ≤ 10^18, b-a ≤ 10^7 və n ≤ 10^7) verilmişdir.

Çıxış verilənləri

Çıxış faylında hasil cəminin 1000000009 modulu üzrə cavabını verin.

Nümunələr