G. Swapstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array of integers a_1, a_2, \dots, a_n (1 \le a_i \le n). You can perform the following operation several (possibly, zero) times:  pick an arbitrary i and perform swap(a_i, a_{a_i}). How many distinct arrays is it possible to attain? Output the answer modulo (10^9 + 7).InputThe first line contains an integer n (1 \le n \le 10^6).The second line contains n integers a_1, a_2, \dots, a_n (1\le a_i\le n).OutputOutput the number of attainable arrays modulo (10^9 + 7).ExamplesInput
31 1 2Output
2
Input
42 1 4 3Output
4
Input
62 3 1 1 1 2Output
18
NoteIn the first example, the initial array is [1, 1, 2]. If we perform the operation with i = 3, we swap a_3 and a_2, obtaining [1, 2, 1]. One can show that there are no other attainable arrays.In the second example, the four attainable arrays are [2, 1, 4, 3], [1, 2, 4, 3], [1, 2, 3, 4], [2, 1, 3, 4]. One can show that there are no other attainable arrays.
31 1 2
2 
['combinatorics', 'dp', 'graphs', 'math', '*2800']