CF1784E.Infinite Game

Alice and Bob are playing an infinite game consisting of sets. Each set consists of rounds. In each round, one of the players wins. The first player to win two rounds in a set wins this set. Thus, a set always ends with the score of $2:0$ or $2:1$ in favor of one of the players.

Let's call a game scenario a finite string $s$ consisting of characters 'a' and 'b'. Consider an infinite string formed with repetitions of string $s$: $sss \ldots$ Suppose that Alice and Bob play rounds according to this infinite string, left to right. If a character of the string $sss \ldots$ is 'a', then Alice wins the round; if it's 'b', Bob wins the round. As soon as one of the players wins two rounds, the set ends in their favor, and a new set starts from the next round.

Let's define $a_i$ as the number of sets won by Alice among the first $i$ sets while playing according to the given scenario. Let's also define $r$ as the limit of ratio $\frac{a_i}{i}$ as $i \rightarrow \infty$. If $r \gt \frac{1}{2}$, we'll say that scenario $s$ is winning for Alice. If $r = \frac{1}{2}$, we'll say that scenario $s$ is tied. If $r \lt \frac{1}{2}$, we'll say that scenario $s$ is winning for Bob.

You are given a string $s$ consisting of characters 'a', 'b', and '?'. Consider all possible ways of replacing every '?' with 'a' or 'b' to obtain a string consisting only of characters 'a' and 'b'. Count how many of them result in a scenario winning for Alice, how many result in a tied scenario, and how many result in a scenario winning for Bob. Print these three numbers modulo $998\,244\,353$.

爱丽丝和鲍勃正在进行一场无限轮次的比赛，比赛由若干局（set）组成。每一局包含若干轮（round）。在每一轮中，其中一名选手获胜。率先在单局中赢得两轮的选手即赢得该局。因此，每一局的最终比分必为 $2:0$ 或 $2:1$，胜者为其中一方。

我们称一个比赛情形（game scenario）为一个仅由字符 'a' 和 'b' 构成的有限字符串 $s$。考虑由该字符串 $s$ 无限重复构成的无限字符串：$sss \ldots$。假设爱丽丝与鲍勃按照该无限字符串从左至右进行每一轮比赛：若字符串 $sss \ldots$ 中某一位是 'a'，则爱丽丝赢得该轮；若是 'b'，则鲍勃赢得该轮。一旦某位选手在当前局中赢得两轮，该局立即结束，胜者即为该局获胜方，并从下一轮开始新一局。

定义 $a_i$ 为按给定情形进行比赛时，前 $i$ 局中爱丽丝获胜的局数。再定义 $r$ 为比值 $\frac{a_i}{i}$ 在 $i \to \infty$ 时的极限。若 $r > \frac{1}{2}$，则称情形 $s$ 对爱丽丝有利（winning for Alice）；若 $r = \frac{1}{2}$，则称情形 $s$ 为平局情形（tied）；若 $r < \frac{1}{2}$，则称情形 $s$ 对鲍勃有利（winning for Bob）。

现给定一个由字符 'a'、'b' 和 '?' 组成的字符串 $s$。考虑所有将每个 '?' 替换为 'a' 或 'b' 的方式，从而得到仅含 'a' 和 'b' 的字符串。统计其中有多少种替换方式使得所得情形对爱丽丝有利，多少种为平局情形，多少种对鲍勃有利。请输出这三个数值对 $998\,244\,353$ 取模的结果。

The only line contains a single string $s$ ($1 \le |s| \le 200$), consisting of characters 'a', 'b', and '?'.

唯一的一行包含一个字符串 $s$（$1 \le |s| \le 200$），由字符 'a'、'b' 和 '?' 组成。

Print three integers: how many ways result in a scenario winning for Alice, how many result in a tied scenario, and how many result in a scenario winning for Bob, modulo $998\,244\,353$.

输出三个整数：分别表示 Alice 获胜的情形数、平局的情形数、Bob 获胜的情形数，结果对 $998\,244\,353$ 取模。

In the first example, there are four ways to replace the question marks:

• $s = \mathtt{aa}$: Alice wins every set $2:0$ — the scenario is winning for Alice;
• $s = \mathtt{ab}$: Alice and Bob win sets in turns, with the score of $2:1$ each — the scenario is tied;
• $s = \mathtt{ba}$: Bob and Alice win sets in turns, with the score of $2:1$ each — the scenario is tied;
• $s = \mathtt{bb}$: Bob wins every set $2:0$ — the scenario is winning for Bob.

在第一个例子中，有四种方式替换问号：

• $s = \mathtt{aa}$：爱丽丝每盘均以 $2:0$ 获胜——该情形对爱丽丝有利；
• $s = \mathtt{ab}$：爱丽丝与鲍勃交替赢下各盘，比分为各 $2:1$——该情形为平局；
• $s = \mathtt{ba}$：鲍勃与爱丽丝交替赢下各盘，比分为各 $2:1$——该情形为平局；
• $s = \mathtt{bb}$：鲍勃每盘均以 $2:0$ 获胜——该情形对鲍勃有利。