Генетический эксперимент
(Время: 2 сек. Память: 64 Мб Сложность: 90%)
Профессор Алексей Владимирович занимается исследованием древней спиральной ДНК, которая сохранилась в образце из вечной мерзлоты. Молекула этой ДНК замкнута в кольцо и имеет N отмеченных точек (эти точки – потенциальные места связывания белков).
Для изучения структуры профессор проводит эксперимент: он добавляет специальные белковые связи, которые могут протянуться строго между двумя различными отмеченными точками и проходят внутри кольца. Каждая новая связь разрывает одну из уже существующих областей молекулы, деля её на две, и тем самым увеличивает количество сегментов ровно на 1.
Профессору нужно понять, сколькими различными способами можно получить в результате эксперимента ровно K сегментов. Порядок, в котором создавались связи, значения не имеет: важен только итоговый набор связей. Так как число вариантов может быть очень велико, профессор берёт остаток по модулю M.
Входные данные
В первой строке входного файла INPUT.TXT находится три натуральных числа N, K, M (3 ≤ N ≤ 108; 1 ≤ K ≤ N–2; 1 < M ≤ 1018).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 3 100 | 5 |
| 2 | 10 6 10 | 7 |
| 3 | 7 1 10 | 1 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
