Kaavi, таинственная гадалка, глубоко верит в то, что судьба человека неизбежна и неотвратима. Конечно, она зарабатывает себе на жизнь предсказывая будущее других людей. Занимаясь гаданием, Kaavi верит, что магические заклинания могут дать ей огромную силу видеть будущее.
У Kaavi есть строка \(T\) длины \(m\) и все строки, имеющие префикс \(T\) это магические заклинания. У Kaavi также есть строка \(S\) длины \(n\) и пустая строка \(A\).
Во время гадания, Kaavi нужно применить некоторую последовательность операций. Есть две различные операции:
- Удалить первый символ строки \(S\) и добавить его в начало строки \(A\).
- Удалить первый символ строки \(S\) и добавить его в конец строки \(A\).
Kaavi может сделать не более, чем \(n\) операций. Для того, чтобы завершить гадание, она хочет узнать количество различных последовательностей операций, для того, чтобы сделать \(A\) магическим заклинанием (то есть эта строка имеет префикс \(T\)). Как ее ассистент, можете ли вы помочь ей? Поскольку ответ может быть очень большим, Kaavi хочет знать его остаток при делении на \(998\,244\,353\).
Две последовательности операций считаются различными, если они различаются по длине или существует такое \(i\), что их \(i\)-е операции различаются.
Подстрокой называется некоторая последовательность последовательных символов строки. Префиксом строки \(S\) называется подстрока \(S\), которая начинается в начале строки \(S\).
Примечание
В первом тесте:
Красные строки это магические заклинания. В первой операции, Kaavi может добавить символ «a» в начало или в конец \(A\). Хотя в обоих случаях результат будет одинаковым, это две разные операции. Поэтому ответ \(6\times2=12\).