Сума добутків#1138
Увійти

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

3 секунди
64 мегабайти
Легка

Дано натуральні числа , та . Ваше завдання — обчислити наступну суму добутків:

a \cdot (a + 1) \cdot \ldots \cdot (a + n - 1) + (a + 1) \cdot (a + 2) \cdot \ldots \cdot (a + n) + \ldots + b \cdot (b + 1) \cdot \ldots \cdot (b + n - 1)

Оскільки результат може бути надзвичайно великим, знайдіть залишок від ділення цієї суми на .

Вхідні дані

Вхідні дані складаються з одного рядка, який містить натуральні числа , та (a \leq b \leq 10^{18}, b - a \leq 10^7, n \leq 10^7).

Вихідні дані

Виведіть знайдену суму добутків за модулем .

Приклади

Приклад 1

Loading
Loading