Допомога Васильку

Прочитавши умову попередньої задачі святий Миколай сказав, що за задачу з такими обмеженнями Василькові в подарок може бути тільки калькулятор, адже його цілком достатньо для знаходження відповіді.

А для справжнього, омріяного подарунку потрібно написати програму, яка б давала відповідь на попередню задачу при більших обмеженнях (N, M, К<=100000).

Оскільки часу залишилося зовсім мало, Василькові нічого не залишається як тільки звернутися до Вас за допомогою. Допоможіть Васильку.

Вхідні дані

В єдиному рядку задано три цілі числа N, M, К.

Вихідні дані

Єдине число – відповідь на поставлену задачу.

Приклади