Alice 和 Bob 正在玩一个由集合组成的无限游戏。每组由回合组成。在每一轮中,一名玩家获胜。在一组比赛中第一个赢得两轮比赛的选手赢得该组比赛。因此,一组比赛总是以其中一名选手的得分 $$$2:0$$$ 或 $$$2:1$$$ 结束。
让我们将游戏场景称为由字符“a”和“b”组成的有限字符串$$$s$$$。考虑由字符串 $$$s$$$ 的重复组成的无限字符串: $$$sss \ldots$$$ 假设 Alice 和 Bob 根据这个无限字符串从左到右玩回合。如果字符串 $$$sss \ldots$$$ 中的一个字符是 'a',那么 Alice 赢得了这一轮;如果是“b”,鲍勃就赢得了这一轮。一旦其中一名球员赢得两轮比赛,该盘比赛就以对他们有利的方式结束,并从下一轮开始新的一盘比赛。
让我们将 $$$a_i$$$ 定义为 Alice 在根据给定场景进行游戏时在前 $$$i$$$ 盘中获胜的盘数。我们还将 $$$r$$$ 定义为比率 $$$\frac{a_i}{i}$$$ 的极限为 $$$i \rightarrow \infty$$$。如果 $$$r > \frac{1}{2}$$$,我们会说场景 $$$s$$$ 为 Alice 获胜。如果 $$$r = \frac{1}{2}$$$,我们会说场景 $$$s$$$ 是平局。如果 $$$r < \frac{1}{2}$$$,我们会说 $$$s$$$ 场景对 Bob 来说是胜利。
给定一个字符串 $$$s$$$,由字符 'a'、'b' 和 '?' 组成。考虑替换每个“?”的所有可能方法与 'a' 或 'b' 一起获取仅由字符 'a' 和 'b' 组成的字符串。计算其中有多少个导致 Alice 获胜的场景,有多少个导致平局的场景,以及有多少个导致 Bob 获胜的场景。打印这三个数字对 $$$998\,244\,353$$$ 取模。
输入
唯一一行包含单个字符串 $$$s$$$ ($$$1 \le |s| \le 200$$$),由字符“a”、“b”和“?”组成。
输出
打印三个整数:有多少种方式导致 Alice 赢得场景,有多少种方式导致平局,以及有多少种方式导致 Bob 场景获胜,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
??
输出 #1
1 2 1
输入 #2
?aa?b
输出 #2
1 3 0
输入 #3
a???ba
输出 #3
4 3 1
输入#4
????????
输出#4
121 14 121
输入 #5
ba????a?a???abbb?
输出 #5
216 57 239
输入 #6
a????a??????b??abbababbbb?a?aaa????bb
输出 #6
97833 28387 135924
输入#7
??????????????a????????????????b?????
输出 #7
484121060 448940322 484613337
注意
第一个例子中,有四种方法来替换问号:
- $$$s = \mathtt{aa}$$$:Alice 赢得每盘 $$$2:0$$$ — 该场景是 Alice 获胜;
- $$$s = \mathtt{ab}$$$:Alice 和 Bob 轮流获胜,得分为 $$$2:1$$$ — 双方打平;
- $$$s = \mathtt{ba}$$$:Bob 和 Alice 轮流获胜,得分为 $$$2:1$$$ — 双方打平;
- $$$s = \mathtt{bb}$$$:鲍勃赢得每盘 $$$2:0$$$ — 该场景是鲍勃获胜。