Informática Avançado - Semana 66

Estradas

João é o rei de N-logândia, ele sabe que o reino é formado por $N$ cidades e $N$ estradas direcionadas. Não necessariamente existe caminho entre duas cidades.

Cada cidade de N-logândia possuí exatamente uma estrada direcionada saindo dela e ligando com outra cidade. João acha as cidades do reino de N-logândia muito confusas, por isso ele vai escolher algumas estradas e mudar o sentido delas. As cidades são consideradas confusas se quando você passa por elas você volta para uma cidade que você já havia passado, ou seja, se a cidade forma um ciclo direcionado.

Por ele achar muito confuso, João decidiu pedir sua ajuda para saber de quantas maneiras diferentes ele pode escolher um conjunto de estradas para inverter de tal forma que nenhuma cidade do reino fique confusa.

Caso você deseje submeter a questão, entre nesse link.

Entrada

A primeira linha de entrada contém um único número inteiro $N$ $(1 \leq N \leq 2 \cdot 10^5)$.

A segunda linha contêm $N$ inteiros $a_1, a_2, a_3, ..., a_n$ $(1 \leq a_i \leq N, a_i \neq i)$, $a_i$ significa que a cidade $i$ possuí uma estrada apontando para a cidade $a_i$.

Saída

Imprima um inteiro representando o número de maneiras que ele pode inverter as cidades, como a resposta pode ser muito grande imprima ela módulo $10^9 + 7$.

Exemplos

ENTRADA	SAÍDA
3 2 3 1	6
4 2 1 1 1	8
5 2 4 2 5 3	28

Explicação

No primeiro exemplo temos o seguinte grafo:

Aqui estão todas as maneiras de inverter as arestas: