G. Swaps
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$). Вы можете выполнить следующую операцию несколько раз (возможно, ни одного):

  • выбрать произвольное $$$i$$$ и выполнить swap$$$(a_i, a_{a_i})$$$.

Сколько различных массивов можно получить? Выведите ответ по модулю $$$(10^9 + 7)$$$.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1\le a_i\le n$$$).

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

Выведите одно число — число достижимых массивов по модулю $$$(10^9 + 7)$$$.

Примеры
Входные данные
3
1 1 2
Выходные данные
2
Входные данные
4
2 1 4 3
Выходные данные
4
Входные данные
6
2 3 1 1 1 2
Выходные данные
18
Примечание

В первом примере изначально массив равен $$$[1, 1, 2]$$$. Если выполнить операцию с $$$i = 3$$$, то местами поменяются значения $$$a_3$$$ и $$$a_2$$$, массив станет равен $$$[1, 2, 1]$$$. Можно показать, что других достижимых массивов нет.

Во втором примере четыре достижимых массива суть $$$[2, 1, 4, 3]$$$, $$$[1, 2, 4, 3]$$$, $$$[1, 2, 3, 4]$$$, $$$[2, 1, 3, 4]$$$. Можно показать, что других достижимых массивов нет.