теория чисел

Недавно директору Ресторана Отеля пришла в голову следующая мысль: <<Все какое-то обычное. Надо что-то модернизировать!>> Именно так и решили заменить всех официантов на роботов или, точнее, робоантов.

Но вот беда! Денег на закупку высококачественного оборудования не нашлось, и партия робоантов была заказана в ОАО <<В Гараже у Петровича>>. И вот теперь, спустя неделю работы по непонятным причинам робоанты начали глючить. Проблема в том, что скоро в Отеле большой банкет. Для его проведения в Ресторане уже расставили \(n\) столов и приготовили \(n\) блюд. Все блюда попарно различны и имеют номера от \(1\) до \(n\). Изначально, блюда по мере готовности как-то расставили по \(n\) столам, причем на каждый стол поставили только одно блюдо. Однако, к банкету необходимо расставить все на свои места, а именно, \(i\)-е блюдо должно оказаться на \(i\)-м столе.

Рядом с каждым столом изначально стоит робоант. Далее каждый робоант независимо от других может выполнять следующую операцию неограниченное число раз: пусть сейчас робоант стоит у \(i\)-го стола. Тогда, если у него с собой нет ни одного блюда, он может взять (а может и не брать) блюдо в данный момент, находящееся на \(i\)-м столе и перейти к любому \(j\)-му столу при условии, что \(i\) и \(j\) имеют общий делитель больший \(1\). Далее, если у робоанта есть с собой блюдо, он может положить его на \(j\)-й стол (а может и не класть).

Теперь директор просит помочь ему у написать программу, которая определит, смогут ли его робоанты расставить все блюда по местам.

Формат входных данных
В первой строке записано одно целое число \(n\) (\(1 \le n \le 200\,000\)) — количество столиков в Ресторане.

Во-второй строке записано \(n\) различных целых чисел \(a_1, a_2, \dots a_n\) (\(1 \le a_i \le n\)) — номера блюд изначально расставленных на соответственно \(1\)-й, \(2\)-й, …\(n\)-й столиках.

Формат выходных данных
Выведите <<YES>>, если робоанты смогут расставить все блюда по местам, и <<NO>> в противном случае случае.

Рассмотрим первый пример: здесь расставить все по местам может один робоант, изначально стоящий у второго стола. Для этого он:

1. Берёт со \(2\)-го стола \(8\)-е блюдо, перемещается к \(8\)-му столу, кладет блюдо.

2. Берёт с \(8\)-го стола \(2\)-е блюдо, перемещается ко \(2\)-му столу, кладет блюдо.

3. Перемещается к \(4\)-му столу.

4. Берёт с \(4\)-го стола \(6\)-е блюдо, перемещается к \(6\)-му столу, кладет блюдо.

5. Берёт с \(6\)-го стола \(4\)-е блюдо, перемещается к \(4\)-му столу, кладет блюдо.

Можно доказать, что во втором примере невозможно расставить все блюда по местам.

Рома, Саша и Алиса решили модернизировать знаменитый алгоритм шифрования RSA. Они считают, что ограничение на модуль \(n\), используемый в RSA, должно быть произведением двух различных простых чисел, избыточно. Вместо этого они планируют использовать \(n\), которое представляет собой произведение степеней \(k\) двух различных простых чисел: \(n = p^kq^k\).

Будем называть нетривиальным разложение числа \(n\) на множители, такое, что множителей хотя бы два, и каждый из них строго больше \(1\). Оказалось, что в случае \(n = p^kq^k\) у числа \(n\) может быть несколько различных нетривиальных разложений на множители. Например, \(100 = 2^2 5^2\) имеет восемь нетривиальных разложений: \(100 = 2\cdot 50\), \(100 = 2\cdot2\cdot25\), \(100 = 2\cdot2\cdot5\cdot5\), \(100=2\cdot5\cdot10\), \(100 = 4\cdot25\), \(100=4\cdot5\cdot5\), \(100=5\cdot20\) и \(100=10\cdot10\).

Теперь ребята задаются вопросом: пусть \(n = p^kq^k\), сколько существует различных нетривиальных разложений \(n\) на множители?

Формат входных данных
На вход подается одно целое число \(n\) (\(6 \le n \le 10^{18}\), гарантируется, что \(n=p^kq^k\) для двух различных \(p\) и \(q\) для целого \(k > 0\)).

Формат выходных данных
Выведите одно число "— количество нетривиальных разложений \(n\) на множители.