G. Исследование Натлана
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы исследуете потрясающий регион Натлан! Этот регион состоит из $$$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
Примечание

В первом примере пять путей следующие:

  • Город $$$1\rightarrow$$$ Город $$$5$$$
  • Город $$$1\rightarrow$$$ Город $$$2\rightarrow$$$ Город $$$5$$$
  • Город $$$1\rightarrow$$$ Город $$$2\rightarrow$$$ Город $$$3\rightarrow$$$ Город $$$5$$$
  • Город $$$1\rightarrow$$$ Город $$$2\rightarrow$$$ Город $$$4\rightarrow$$$ Город $$$5$$$
  • Город $$$1\rightarrow$$$ Город $$$4\rightarrow$$$ Город $$$5$$$

Во втором примере два пути следующие:

  • Город $$$1\rightarrow$$$ Город $$$3\rightarrow$$$ Город $$$5$$$
  • Город $$$1\rightarrow$$$ Город $$$2\rightarrow$$$ Город $$$3\rightarrow$$$ Город $$$5$$$