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$$$.