Задача 70. Дивное волненье ≡

Условие

Моцарт в легком опьяненье

Шел домой.

Было дивное волненье,

День шальной.

И глядел веселым оком

На людей

Композитор Моцарт Вольфганг

Амадей.

...

Давид Самойлов, "Дуэт для скрипки и альта", 1981 г.

Художественное исполнение

Моцарт в приподнятом расположении духа возвращается домой (ещё бы — две пьесы за два дня и две ночи, это не шутка). Встречая мужчину, он учтиво приподнимает шляпу, и его настроение повышается на a. Встречая женщину, он приветливо улыбается, и его настроение увеличивается на b. Сколько существует различных наборов встречных прохожих, если всего за время прогулки настроение композитора выросло на n?

Формат входных данных

Единственная строка входного файла содержит три натуральных числа a, b и n, записанных через пробел.

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ a, b ≤ 1000

1 ≤ n ≤ 10¹⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 10⁵, получат не менее 40 баллов.

Пояснения к примерам

В первом примере a = 2, b = 3 и n = 15. Моцарт мог встретить:

1) 0 мужчин и 5 женщин;

2) 3 мужчин и 3 женщин.

3) 6 мужчин и 1 женщину.

Всего три набора.

Во втором примере настроение всегда увеличивается на чётное число, а n = 15 — нечётное.

Примеры тестов

2 3 15

3

2 4 15

0