Алиса и Боб играют в бесконечную игру, состоящую из сетов. Каждый сет состоит из раундов. В каждом раунде выигрывает один из игроков. В сете выигрывает тот, кто первым выиграет два раунда. Соответственно, сет всегда заканчивается со счётом $$$2:0$$$ или $$$2:1$$$ по раундам в пользу одного из игроков.

Сценарием игры назовём конечную строку $$$s$$$ из символов «a» и «b». Рассмотрим бесконечную строку, образованную повторениями строки $$$s$$$: $$$sss \ldots$$$ Пусть игроки играют раунды в соответствии с этой бесконечной строкой по порядку. Если очередной символ строки $$$sss \ldots$$$ равен «a», то в текущем раунде выигрывает Алиса, если «b» — выигрывает Боб. Как только один из игроков выигрывает два раунда, сет завершается в его пользу, и со следующего раунда начинается новый сет.

Пусть $$$a_i$$$ равно числу выигранных Алисой сетов среди первых $$$i$$$ сетов при игре по данному сценарию. Обозначим через $$$r$$$ предел отношения $$$\frac{a_i}{i}$$$ при $$$i \rightarrow \infty$$$. Если $$$r > \frac{1}{2}$$$, то строку $$$s$$$ назовём выигрышным для Алисы сценарием. Если $$$r = \frac{1}{2}$$$, то строку $$$s$$$ назовём ничейным сценарием. Если $$$r < \frac{1}{2}$$$, то строку $$$s$$$ назовём выигрышным для Боба сценарием.

Вам дана строка $$$s$$$, состоящая из символов «a», «b» и «?». Рассмотрим все способы заменить каждый символ «?» на «a» или «b», чтобы получить строку, состоящую только из символов «a» и «b». Посчитайте, в скольких случаях получится выигрышный для Алисы сценарий, в скольких — ничейный, а в скольких — выигрышный для Боба, и выведите эти три числа по модулю $$$998\,244\,353$$$.