Добраться до сюда в контесте было непросто. Решив все предыдущие задачи, вы произвели большое впечатление на богов. Поэтому, они решили избавить вас от истории в этой задаче и вместо этого дать вам формальное условие.

Рассмотрим $$$n$$$ агентов. У каждого из них изначально есть ровно один предмет, у $$$i$$$-го агента есть предмет номер $$$i$$$. Мы хотим переназначить предметы между агентами. Назначение будет валидным, если каждый предмет назначен ровно одному агенту, и у каждого агента есть ровно один предмет.

У каждого агента есть предпочтения одних предметов перед другими, которое может быть выражено перестановкой $$$p$$$ элементов, отсортированных от наиболее желанных до наименее желанных. Другими словами, агент предпочитает предмет $$$i$$$ предмету $$$j$$$, если $$$i$$$ появляется раньше в его перестановке $$$p$$$. Профиль предпочтений это список из $$$n$$$ перестановок длины $$$n$$$ каждая, $$$i$$$-я перестановка описывает предпочтения $$$i$$$-го агента.

Возможно, что некоторые агенты недовольны назначенными им предметами. Множество недовольных агентов может выбрать не кооперироваться с другими агентами. В таком случае, они обменяются теми предметами, которые у них были изначально ($$$i$$$-му агенту принадлежал $$$i$$$-й предмет), только между собой. Агенты из группы не волнуются об удовлетворенности агентов вне группы. Однако, они должны обменяться предметами так, чтобы как минимум один из них стал счастливее, и никто не стал менее счастливым (по сравнению с назначением, которое было сделано).

Формально, рассмотрим валидное назначение элементов — $$$A$$$. Скажем, что $$$A(i)$$$ обозначает предмет, назначенный $$$i$$$-му агенту. Также, рассмотрим подмножество агентов. Пусть $$$S$$$ будет множеством их индексов. Скажем, что это подмножество агентов недовольно, если существует такое валидное назначение элементов $$$B(i)$$$, что:

• Для всех $$$i \in S$$$, $$$B(i) \in S$$$.
• Ни один агент $$$i \in S$$$ не предпочитает предмет $$$A(i)$$$ предмету $$$B(i)$$$ (ни один агент из $$$S$$$ не менее счастлив).
• Как минимум один агент $$$i \in S$$$ предпочитает предмет $$$B(i)$$$ предмету $$$A(i)$$$ (как минимум один агент из $$$S$$$ более счастлив).

Назначение оптимально, если ни одно подмножество агентов не недовольно. Обратите внимание, что пустое подмножество не может быть недовольно. Можно доказать, что для каждого профиля предпочтений существует ровно одно оптимальное назначение.

Пример: Рассмотрим $$$3$$$ агентов со следующими профилями предпочтений:

1. $$$[2, 1, 3]$$$
2. $$$[1, 2, 3]$$$
3. $$$[1, 3, 2]$$$

И следующее назначение:

• Первый агент получает предмет $$$2$$$
• Второй агент получает предмет $$$3$$$.
• Третий агент получает предмет $$$1$$$.

Заметьте, что множество агентов $$$\{1, 2\}$$$ является недовольным, потому что они могут переупорядочить их (исходные) предметы следующим образом:

• Первый агент получает предмет $$$2$$$.
• Второй агент получает предмет $$$1$$$.
• Третий агент получает предмет $$$3$$$.

Это назначение сделает второго агента более счастливым, и не имеет разницы для первого агента. В результате, третий агент получит предмет, который хуже для него, но это не влияет на то, что множество $$$\{1,2\}$$$ будет недовольно (он не лежит в этом множестве).

Следующее назначение будет оптимальным:

• Первый агент получает предмет $$$2$$$.
• Второй агент получает предмет $$$1$$$.
• Третий агент получает предмет $$$3$$$.

Дано назначение $$$A$$$, вычислите количество различных профилей предпочтений, для которых это назначение $$$A$$$ является оптимальным. Так как ответ может быть большим, выведите его по модулю $$$10^9+7$$$.

Два профиля предпочтений считаются различными, если есть агент, у которого различается перестановка предпочтений.