ttim.info

Начинаем публикацию заданий с республиканской олимпиады школьников по информатике за 2007 год.

Задание второе с 1 тура:

Пусть даны две перестановки A и B длины N. Назовем произведением престановки A на B такую перестановку C, что C[i] = A[B[i]].

Например (3, 2, 4, 1)*(1, 3, 4, 2) = (3, 4, 1, 2), а (1, 3, 4, 2)*(3, 2, 4, 1) = (4, 3, 2, 1).

Для заданной перестановки A найти количесто перестановок B таких что A*B = B*A. Ответ вывести по модулю P.

Input
permutation.in N P перестановка A

Output
permutation.out ответ по модулю P

Ограничения N <= 100000, P <= 1000000

Пример.
permutation.in
5 100
1 2 3 4 5

permutation.out
20

Пояcнение: Так как ответ 120 (вск возможные перестановки длины 5), то вывести надо 20 (120 по модулю 100).

решения скидывайте в комменты. Тесты есть, могу проверить