Вы исследуете потрясающий регион Натлан! Этот регион состоит из \(n\) городов, и каждый город имеет рейтинг привлекательности \(a_i\). Направленное ребро существует от города \(i\) к городу \(j\) тогда и только тогда, когда \(i < j\) и \(\gcd(a_i,a_j)\neq 1\), где \(\gcd(x, y)\) обозначает наибольший общий делитель (НОД) целых чисел \(x\) и \(y\).
Начав с города \(1\), ваша задача — определить общее количество различных путей, которыми вы можете добраться до города \(n\), по модулю \(998\,244\,353\). Два пути различны тогда и только тогда, когда множество посещённых городов различно.
Первая строка содержит целое число \(n\) (\(2 \leq n \leq 2 \cdot 10^5\)) — количество городов.
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(2 \leq a_i \leq 10^6\)) — привлекательность каждого города.
Выведите общее количество различных путей, которыми вы можете добраться до города \(n\), по модулю \(998\,244\,353\).
В первом примере пять путей следующие:
Во втором примере два пути следующие:
5 2 6 3 4 6
5
5 4 196 2662 2197 121
2
7 3 6 8 9 11 12 20
7
2 2 3
0
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач