Задача F. Перекрашивание шушанчиков ≡

Условие

У Крокодила Гены есть N чемоданов с шушанчиками, пронумерованных от 1 до N. В чемодане с номером i находится i шушанчиков.

Главное развлечение Крокодила Гены — перекрашивание шушанчиков. Процесс перекрашивания заключается в следующем: Гена произвольно выбирает ненулевое количество шушанчиков из какого-нибудь чемодана, берет i миллилитров краски, где i — номер выбранного чемодана, и тратит её всю на выбранных шушанчиков.

Крокодил Гена не любит делать одно и то же дважды, поэтому если некоторый набор шушанчиков он уже красил, больше он этот набор не выберет (тем не менее, один и тот же шушанчик может быть перекрашен более одного раза в составе разных наборов).

Очевидно, что когда-нибудь Крокодил Гена перекрасит все возможные наборы шушанчиков из всех чемоданов. Вопрос лишь в том, сколько краски он на это потратит. Ответ может оказаться очень большим числом, поэтому найдите лишь его остаток от деления на заданное M.

Формат входного файла

Формат выходного файла

Выведите единственное число — остаток от деления количества миллилитров краски на M.

В первом примере существует единственный набор из одного шушанчика, поэтому ответ 1. Во втором примере Гене потребуется 7 миллилитров краски (1 × 1 + 2 × 3), а остаток от деления 7 на 5 есть 2.

Ограничения

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

1 1000000000

1

2 5

2