ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1696. Зарплата для роботов

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
На планете PTZZZ живёт и работает n роботов. С незапамятных времён на планете существует строгая иерархия: каждый робот имеет свой уникальный ранг — целое число от 1 до n, и обязан подчиняться приказам всех роботов с большим рангом.
Ровно один раз в месяц роботы получают за свою работу зарплату размером от 1 до k кредитов. Начислением зарплаты занимается робот-бухгалтер. Механизм получения зарплаты стал настолько важен для роботов, что они даже привязали к нему своё летоисчисление. Так, первый месяц, за который все роботы планеты впервые получили зарплату, был назван Первым месяцем Первого года. Всего в году планеты PTZZZ p месяцев, так что роботы получают зарплату целых p раз в год!
Размер зарплаты каждого из роботов может меняться от месяца к месяцу. Более того, если окажется так, что за какой-то месяц всем роботам выдана в точности та же зарплата, как за какой-то месяц ранее, то робот-бухгалтер заржавеет от горя. Кроме того, закон не позволяет роботу-бухгалтеру так распределить кредиты, чтобы существовала такая тройка роботов (a, b, c), что ранг a больше, чем ранг b, и ранг b больше, чем ранг c, но при этом a получил зарплату меньше, чем b, а b — меньше, чем c.
Робот-бухгалтер хочет не ржаветь от горя как можно дольше, поэтому, начиная с Первого месяца Первого года, он старается каждый месяц выплачивать различную конфигурацию зарплаты. Однако, как легко понять, различных допустимых конфигураций зарплаты всё же конечное число, поэтому роботу-бухгалтеру в конце концов придётся заржаветь. От Вас требуется лишь найти номер месяца, в который это произойдёт.

Исходные данные

В единственной строке даны три целых числа через пробел: n, k и p — количество роботов на планете PTZZZ, максимальный возможный размер зарплаты робота и количество месяцев в году роботов соответственно (1 ≤ n ≤ 1000; 1 ≤ k ≤ 200; 2 ≤ p ≤ 109).

Результат

Выведите номер месяца, в который робот-бухгалтер вынужден будет заржаветь от горя. Месяцы года нумеруются от 1 до p.

Пример

исходные данныерезультат
3 3 20
7
Автор задачи: Игорь Чевдарь
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, February 2009