无限比赛

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

Alice 与 Bob 进行无限多局比赛。每局由若干轮组成，先赢得两轮的玩家赢得该局，因此比分总为 $2:0$ 或 $2:1$。

一个只含 a、b 的有限字符串 $s$ 会无限重复为 $sss\ldots$。从左到右读取字符：a 表示 Alice 赢得该轮，b 表示 Bob 赢得该轮；一局结束后立刻从下一个字符开始新一局。

令 $a_i$ 为前 $i$ 局中 Alice 获胜的局数，并令 $r=\lim_{i\to\infty}a_i/i$。若 $r>1/2$，场景对 Alice 有利；若 $r=1/2$，为平局；否则对 Bob 有利。

现在给定只含 a、b、? 的模式串。把每个 ? 独立替换成 a 或 b，分别统计对 Alice 有利、平局、对 Bob 有利的替换方案数，答案对 $998244353$ 取模。

输入格式

一行一个字符串 $s$。

输出格式

输出三个整数，依次表示 Alice 有利、平局、Bob 有利的方案数。

样例输入 1

??

样例输出 1

1 2 1

样例输入 2

?aa?b

样例输出 2

1 3 0

样例输入 3

a???ba

样例输出 3

4 3 1

数据范围

对于全部数据，$1\le |s|\le200$。

题目来源：Codeforces 1784E。