Вы исследуете потрясающий регион Натлан! Этот регион состоит из \(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\), по модулю \(998\,244\,353\).
Примечание
В первом примере пять путей следующие:
- Город \(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\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 6 3 4 6
|
5
|
|
2
|
5
4 196 2662 2197 121
|
2
|
|
3
|
7
3 6 8 9 11 12 20
|
7
|
|
4
|
2
2 3
|
0
|