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~) = (~ab_1~,~ab_2~, ~ab_3~, …, ~ab_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