| Автор: | И. Туфанов | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt |
У Крокодила Гены есть N чемоданов с шушанчиками, пронумерованных от 1 до N. В чемодане с номером i находится i шушанчиков.
Главное развлечение Крокодила Гены — перекрашивание шушанчиков. Процесс перекрашивания заключается в следующем: Гена произвольно выбирает ненулевое количество шушанчиков из какого-нибудь чемодана, берет i миллилитров краски, где i — номер выбранного чемодана, и тратит её всю на выбранных шушанчиков.
Крокодил Гена не любит делать одно и то же дважды, поэтому если некоторый набор шушанчиков он уже красил, больше он этот набор не выберет (тем не менее, один и тот же шушанчик может быть перекрашен более одного раза в составе разных наборов).
Очевидно, что когда-нибудь Крокодил Гена перекрасит все возможные наборы шушанчиков из всех чемоданов. Вопрос лишь в том, сколько краски он на это потратит. Ответ может оказаться очень большим числом, поэтому найдите лишь его остаток от деления на заданное M.
Выведите единственное число — остаток от деления количества миллилитров краски на M.
В первом примере существует единственный набор из одного шушанчика, поэтому ответ 1. Во втором примере Гене потребуется 7 миллилитров краски (1 × 1 + 2 × 3), а остаток от деления 7 на 5 есть 2.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|