Вам даны два целых числа \(n\) и \(m\) и массив \(a\) из \(n\) целых чисел. Для каждого \(1 \le i \le n\) верно, что \(1 \le a_i \le m\).
Ваша задача — посчитать количество различных массивов \(b\) длины \(n\) таких, что:
- \(1 \le b_i \le m\) для каждого \(1 \le i \le n\), и при этом
- \(\gcd(b_1,b_2,b_3,...,b_i) = a_i\) для каждого \(1 \le i \le n\).
Здесь \(\gcd(a_1,a_2,\dots,a_i)\) обозначает наибольший общий делитель (НОД) целых чисел \(a_1,a_2,\ldots,a_i\).
Так как это число может быть слишком большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите единственное целое число — количество различных массивов, удовлетворяющих приведенным выше условиям. Так как это число может быть большим, выведите его по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных допустимыми массивами \(b\) являются:
- \([4,2,1]\);
- \([4,2,3]\);
- \([4,2,5]\).
Во втором наборе входных данных единственным массивом, удовлетворяющим требованиям, является \([1,1]\).
В третьем наборе входных данных можно доказать, что такого массива не существует.
В третьем и четвертом тестовых примерах есть красивые объяснения, но, к сожалению, они слишком длинные, чтобы их писать, поэтому мы просим вас поверить нам.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2
|
3
1
0
595458194
200000000
|