Алиса и Боб играют в бесконечную игру, состоящую из сетов. Каждый сет состоит из раундов. В каждом раунде выигрывает один из игроков. В сете выигрывает тот, кто первым выиграет два раунда. Соответственно, сет всегда заканчивается со счётом \(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\).
Выходные данные
Выведите три числа: сколько способов замены приведут к выигрышному для Алисы сценарию, сколько — к ничейному, а сколько — к выигрышному для Боба. Все числа нужно вывести по модулю \(998\,244\,353\).