Giải bài trực tuyến

                Nam 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₁, a₂, a₃, … , a_n) và (b₁, b₂, b₃, … ,b_n) được định nghĩa như sau
            (a₁, a₂, a₃, … , a_n) x (b₁, b₂, b₃, … ,b_n) = (a_b1,a_b2, a_b3, …, a_bn)
            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₁, a₂, a₃, … , a_n)² = (a₁, a₂, a₃, … , a_n) x (a₁, a₂, a₃, … , a_n)
            (a₁, a₂, a₃, … , a_n)^k = (a₁, a₂, a₃, … , a_n) x (a₁, a₂, a₃, … , a_n) x … x (a₁, a₂, a₃, … , a_n)  (k phép nhân hoán vị) 

            Nam nhận thấy có những số nguyên X mà (a₁, a₂, a₃, … , a_n)^X = (a₁, a₂, a₃, … , a_n). Khi đó ta gọi X là một chu trình của (a₁, a₂, a₃, … , a_n).
            Với một một hoán vị ban đầu (a₁, a₂, a₃, … , a_n). Nam 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₁, a₂, a₃, … , a_n). Hãy giúp Nam.

Input

            Dòng đầu ghi số nguyên dương N (1 <= N <= 2x10⁶)
            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.

Output

                Gồm một số nguyên M duy nhất là số dư của K cho 10⁹+7.       
            Dữ liệu vào bảo đảm có kết quả.
            Trong 30% số test có N <= 500,  K <= 5x10⁵
            Trong 50% số test, K <= 10¹⁸

Example

Input:
5
5 3 2 1 4

Output:

6

Input:

5

1 2 3 4 5

Output:

1

Input:

5

5 4 3 2 1

Output:

2