Bờm rất thích hoán vị. Một hoán vị N là một cách sắp xếp N số nguyên dương từ 1 đến N, mỗi số chỉ xuất hiện một lần. Ví dụ 1 3 5 2 4 là một hoán vị 5. Phép nhân 2 hoán vị N ($a_1$, $a_2$, $a_3$, … , $a_n$) và ($b_1$, $b_2$, $b_3$, … ,$b_n$) được định nghĩa như sau: ($a_1$, $a_2$, $a_3$, … , $a_n$) x ($b_1$, $b_2$, $b_3$, … ,$b_n$) = ($a{b}_1$,$a{b}_2$, $a{b}_3$, …, $a{b}_n$)

Ví dụ : (2 5 1 4 3) x (3 4 2 5 1) = (1 4 5 3 2) Phép lũy thừa hoán vị được định nghĩa theo phép nhân hoán vị : ($a_1$, $a_2$, $a_3$, … , $a_n$)2 = ($a_1$, $a_2$, $a_3$, … , $a_n$) x ($a_1$, $a_2$, $a_3$, … , $a_n$) ($a_1$, $a_2$, $a_3$, … , $a_n$)k = ($a_1$, $a_2$, $a_3$, … , $a_n$) x ($a_1$, $a_2$, $a_3$, … , $a_n$) x … x ($a_1$, $a_2$, $a_3$, … , $a_n$) (k phép nhân hoán vị).

Bờm nhận thấy có những số nguyên X mà ($a_1$, $a_2$, $a_3$, … , $a_n$)X = ($a_1$, $a_2$, $a_3$, … , $a_n$). Khi đó ta gọi X là một chu trình của ($a_1$, $a_2$, $a_3$, … , $a_n$). Với một một hoán vị ban đầu ($a_1$, $a_2$, $a_3$, … , $a_n$). Bờm muốn tìm số nguyên dương K nhỏ nhất sao cho K+1 là một chu trình của ($a_1$, $a_2$, $a_3$, … , $a_n$). Hãy giúp Bờm.

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương N (1 <= N <= 2x${10}^5$).
• Dòng thứ 2 gồm N số nguyên dương khác nhau đôi một thể hiện hoán vị ban đầu.

Kết quả:

• Gồm một số nguyên M duy nhất là số dư của K cho ${10}^9$+7.

Ví dụ:

INPUT 1

5
5 3 2 1 4

OUPUT 1

6

INPUT 2

5
1 2 3 4 5

OUPUT 2

1