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_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~) và (~b_{1}~, ~b_{2}~, ~b_{3}~, ~\cdots~, ~b_{n}~) được định nghĩa như sau

(~a_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~) ~\times~ (~b_{1}~, ~b_{2}~, ~b_{3}~, ~\cdots~, ~b_{n}~) = (~a_{b1}~,~a_{b2}~, ~a_{b3}~, ~\cdots~, ~a_{bn}~)

Ví dụ : (~2~, ~5~, ~1~, ~4~, ~3~) ~\times~ (~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}~, ~\cdots~, ~a_{n}~)~^ 2~ = (~a_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~) ~\times~ (~a_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~)

(~a_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~)~^k~ = (~a_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~) ~\times~ (~a_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~) ~\times \cdots \times~ (~a_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~)  (~k~ phép nhân hoán vị)

Nam nhận thấy có những số nguyên ~X~ mà (~a_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~ )~^X~ = (~a_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~). Khi đó ta gọi ~X~ là một chu trình của (~a_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~).

Với một một hoán vị ban đầu (~a_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~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_{1}~, ~a_{2}~, ~a_{3}~, ~\cdots~, ~a_{n}~). Hãy giúp Nam.

Input

Dòng đầu ghi số nguyên dương ~N~ (~1~ ~\le~ ~N~ ~\le~ ~2 \times 10^{6}~)

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^{9} + 7~.

Dữ liệu vào bảo đảm có kết quả.

Giới hạn

Trong 30% số test có ~N \le 500~,  ~K \le 5 \times 10^{5}~.

Trong 50% số test, ~K~ ~\le~ ~10^{18}~.

Sample Input 1

5
5 3 2 1 4

Sample Output 1

6

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1

Sample Input 3

5
5 4 3 2 1

Sample Output 3

2