eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Зарплата для роботів

Зарплата для роботів

Ліміт часу 2 секунди
Ліміт використання пам'яті 16 MiB

На планеті PTZZZ живе і працює n роботів. З незапам'ятних часів на планеті існує строга ієерархія: кожен робот має свій унікальний ранг — ціле число від 1 до n, і зобов'язаний підкорятись наказам усіх роботів з більшим рангом.

Рівно один раз в місяць роботи отримують за свою роботу зарплату розміром від 1 до k кредитів. Нарахуванням зарплати займається робот-бухгалтер. Механізм отримання зарплати став настільки важливим для роботів, що вони навіть прив'язали до нього своє літочислення. Так, перший місяць, за який усі роботи планети вперше отримали зарплату, було названо Першим місяцем Першого року. Усього в році планети PTZZZ p місяців, так що роботи отримують зарплату цілих p разів на рік!

Розмір зарплати кожного з роботів може змінюватись від місяця до місяця. Більше того, якщо виявиться так, що за якийсь місяць усім роботам видано у точності таку ж зарплату, як і за якийсь місяць раніше, то робот-бухгалтер заіржавіє від горя. Крім того, закон не дозволяє роботу-бухгалтеру так розподіляти кредити, щоб існувала така трійка роботів (a, b, c), що ранг a більше, ніж ранг b, і ранг b більше, ніж ранг c, але при цьому a отримав зарплату менше, ніж b, а b — менше, ніж c.

Робот-бухгалтер хоче не іржавіти від горя якомога довше, тому, починаючи з Першого місяця Першого року, він намагається кожен місяць виплачувати різну конфігурацію зарплати. Проте, як легко зрозуміти, різних допустимих конфігурацій зарплати усе ж скінченне число, тому роботу-бухгалтеру у кінці кінців доведеться заіржавіти. Від Вас вимагається лише знайти номер місяця, у який це відбудеться.

Вхідні дані

У єдиному рядку задано три цілих числа через пропуск: n, k та p — кількість роботів на планеті PTZZZ, максимально можливий розмір зарплати робота та кількість місяців у році роботів відповідно (1n1000; 1k200; 2p10^9).

Вихідні дані

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

Приклад

Вхідні дані #1
3 3 20
Вихідні дані #1
7
Автор Ігор Чевдарь
Джерело Ural SU Contest. Petrozavodsk Winter Session, February 2009