Có một mảng đã sắp xếp \([1,2,\dots,n]\) và một hoán vị \(p_1,p_2,\dots,p_n\). Ở mỗi vòng, tất cả phần tử di chuyển theo hoán vị: phần tử ở vị trí \(i\) di chuyển đến vị trí \(p_i\).

Sau bao nhiêu vòng thì mảng được sắp xếp lại như ban đầu lần đầu tiên?

Input

Dòng đầu tiên chứa một số nguyên \(n\).

Dòng tiếp theo chứa \(n\) số nguyên \(p_1,p_2,\dots,p_n\).

Output

In ra số vòng lấy modulo \(10^9+7\).

Constraints

• \(1 \le n \le 2 \cdot 10^5\)

Example

8
5 3 2 6 4 1 8 7

4

Giải thích: Mảng thay đổi như sau sau các vòng:

• Vòng 1: \([6,3,2,5,1,4,8,7]\)

• Vòng 2: \([4,2,3,1,6,5,7,8]\)

• Vòng 3: \([5,3,2,6,4,1,8,7]\)

• Vòng 4: \([1,2,3,4,5,6,7,8]\)