Рик и Морти путешествуют по мультивселенной. В мире Рика и Морти существуют $n$ вселенных. Недавно Морти захотел узнать, сколько вообще существует вариантов их с Риком путешествий по мультивселенной (путешествие — обход всех вселенных в каком-то порядке). Так как Морти не очень умный, а число вселенных большое, он ограничится количеством путешествий по модулю $m$. Более того, как вы знаете существуют клоны Морти. Поэтому за помощью к вам пришел не один Морти, а целых три. Помогите им в их тяжелом занятии.

Входные данные

На вход поступают три строки, каждая из которых содержит два целых числа $n$, $m$ ($1 \le n \le 10^{18}$, $1 \le m \le 10^6$).

Выходные данные

Вывести 3 числа — ответ для каждого из Морти.

Подзадачи