Існує відсортований масив ~[1,2,\dots,n]~ і перестановка ~p_1,p_2,\dots,p_n~.

У кожному раунді всі елементи переміщуються відповідно до перестановки: елемент у позиції ~i~ переміщується в позицію ~p_i~.

Після скількох раундів масив знову сортується вперше?

Обмеження

• ~1 \le n \le 2 \cdot 10^5~

Формат вхідних даних

У першому рядку є ціле число ~n~.

Наступний рядок містить ~n~ цілих чисел ~p_1,p_2,\dots,p_n~.

Формат вихідних даних

Виведіть кількість раундів за модулем 10^9+7.

Приклад вхідних даних

8
5 3 2 6 4 1 8 7

Приклад вихідних даних

4

Пояснення: після раундів масив змінюється таким чином:

• Раунд 1: [6,3,2,5,1,4,8,7]
• Раунд 2: [4,2,3,1,6,5,7,8]
• Раунд 3: [5,3,2,6,4,1,8,7]
• Раунд 4: [1,2,3,4,5,6,7,8]