Рік і Морті подорожують у мультивсесвіті. У світі Ріка і Морті існують ~n~ всесвітів. Нещодавно Морті захотів дізнатися, скільки взагалі існує варіантів їх з Ріком подорожей по мультивсесвіту (подорож - обхід всіх всесвітів в якомусь порядку). Так як Морті не надто розумний, а число всесвітів велике, він обмежиться кількістю подорожей по модулю ~m~. Більш того, як ви знаєте, існують клони Морті. Тому за допомогою до вас прийшов не один Морті, а цілих три. Допоможіть їм виконати це завдання.

Input

На вхід надходять три рядки, кожен з яких містить два цілих числа ~n~, ~m~ (~1 \le n \le 10^{18}~, ~1 \le m \le 10^6~).

Output

Вивести 3 числа - відповідь для кожного з Морті.

Sample Input 1

1 2
3 7
3 6

Sample Output 1

1
6
0

Notes

Пояснення до тесту з умови. Для n = 1 існує тільки один обхід - відвідати перший всесвіт, для n = 3 існує 6 різних обходів (123, 132, 213, 231, 321, 312), тому по модулю 6 це 0, а по модулю 7 - 6.