Vòng Quay

Cho $n$ thẻ bài được đánh số từ $1$ đến $n$, ban đầu được xếp tương ứng tại các vị trí từ $1$ đến $n$. Trong mỗi bước biến đổi, thẻ bài ở vị trí $i$ sẽ di chuyển sang vị trí $p_i$.

Hãy tính số bước biến đổi ít nhất để tất cả các thẻ bài đều quay trở lại vị trí ban đầu. Vì kết quả có thể rất lớn, hãy in ra đáp số sau khi chia lấy dư cho $10^9+7$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ ($1 ≤ n ≤ 2 · 10^5$).

Dòng thứ hai chứa $n$ số nguyên $p_1, p_2, ..., p_n$ tạo thành một hoán vị của $1, 2, ..., n$.

Kết quả

In ra một số nguyên duy nhất là số bước biến đổi ít nhất sau khi chia lấy dư cho $10^9+7$.

Chấm điểm

Subtask 1 (20 points). $n ≤ 10$

Subtask 2 (80 points). $1 ≤ n ≤ 2 · 10^5$

Ví dụ

Input

5
2 1 4 5 3

Output

6

Ghi chú

Trong ví dụ trên, trạng thái danh sách thẻ bài qua từng bước thay đổi như sau:

Bước 1: [2, 1, 5, 3, 4]

Bước 2: [1, 2, 4, 5, 3]

Bước 3: [2, 1, 3, 4, 5]

Bước 4: [1, 2, 5, 3, 4]

Bước 5: [2, 1, 4, 5, 3]

Bước 6: [1, 2, 3, 4, 5]