В Тридвоичном царстве Тритроичном государстве жил-был Царь. Недолго ему осталось жить на этом свете, и решил Царь в последний раз объехать свои владения — посмотреть, что в них происходит.

В государстве n городов, между любыми двумя городами проложена ровно одна двусторонняя дорога. Один из городов является столицей, и Царь живёт именно там.

Царь очень стар, и склероз все чаще даёт знать о себе. Поэтому Царь принял решение объехать все города таким образом, чтобы побывать в каждом ровно по два раза, на всякий случай. Путь должен начинаться в столице и заканчиваться в ней же.

Пока Царь выбирал наилучший вариант путешествия, он столкнулся с одним интересным вопросом, который теперь не даёт ему покоя: сколько существует различных маршрутов, удовлетворяющих вышеперечисленным условиям?

В первой строке через пробел записаны целые числа n и p (3 ≤ n ≤ 10⁵; 1 ≤ p ≤ 10⁹ + 7).

Выведите ответ на вопрос Царя по модулю p.