Патрик называет подстроку\(^\dagger\) бинарной строки\(^\ddagger\) хорошей, если эта подстрока содержит ровно одну 1.
Помогите Патрику посчитать количество бинарных строк \(s\), таких что \(s\) содержит ровно \(n\) хороших подстрок и не имеет хороших подстрок длины строго больше \(k\). Обратите внимание, что подстроки различаются по их расположению в строке, например, если \(s =\) 1010, вы должны посчитать оба вхождения 10.
\(^\dagger\) Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
\(^\ddagger\) Бинарная строка — это строка, которая содержит только символы 0 и 1.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество бинарных строк \(s\), таких что \(s\) содержит ровно \(n\) хороших подстрок и не имеет хороших подстрок длины строго больше \(k\). Поскольку это число может быть слишком большим, выведите его по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных единственной подходящей бинарной строкой является 1. Строка 01 не подходит, потому что она содержит подстроку 01 длины \(2 > 1\).
Во втором наборе входных данных подходящими бинарными строками являются 011, 110 и 111.
В третьем наборе входных данных подходящими бинарными строками являются 101, 0110, 0111, 1110, 1111.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 1
3 2
4 2
5 4
6 2
2450 2391
|
1
3
5
12
9
259280854
|