Недавно Мориарти напал на след Шерлока и смог получить данные о важном событии, которое произойдёт ровно тогда, когда по некоторому высокочастотному радиосигналу будет передана в точности строка $$$S$$$.
Однако на этот раз Шерлоку удалось запутать своего главного врага, и он специально передал Мориарти эти сведения. Вместо полезной информации он каждую секунду будет равновероятно отправлять один из символов своего алфавита шифровки. В это время Мориарти будет ждать, пока в строке из полученных символов не появится подстрока, равная $$$S$$$; после этого он тут же прекратит наблюдения.
Сейчас Шерлок очень занят, поэтому он попросил вас определить математическое ожидание количества секунд, которое Мориарти будет наблюдать, пока в потоке не появится строка $$$S$$$. Ответ выведите по модулю $$$998244353$$$.
Первая строка содержит строку $$$A$$$ ($$$1 \le |A| \le 36$$$), состоящую из строчных латинских букв или цифр, которая представляет набор символов, которые Шерлок будет равновероятно передавать. Гарантируется, что все символы $$$A$$$ различны.
Вторая строка содержит строку $$$S$$$ ($$$1 \le |S| \le 5 \cdot 10^5$$$), которая является последовательностью символов, появления которой будет ждать Мориарти. Гарантируется, что все символы $$$S$$$ содержатся среди символов строки $$$A$$$.
В единственной строке выведите математическое ожидание числа секунд, которое будет ждать Мориарти, по модулю $$$998244353$$$.
011
2
aboaboba
246
andrew13andrew13
16777216
| Весенний кубок МИФИ 2025 |
|---|
| Закончено |
