Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

combinatorics

dp

games

probabilities

*3100

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Infinite Game

time limit per test

5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputAlice 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 > \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 < \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$$$.

Input

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

Output

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$$$.

Examples

Input

??

Output

1 2 1

Input

?aa?b

Output

1 3 0

Input

a???ba

Output

4 3 1

Input

????????

Output

121 14 121

Input

ba????a?a???abbb?

Output

216 57 239

Input

a????a??????b??abbababbbb?a?aaa????bb

Output

97833 28387 135924

Input

??????????????a????????????????b?????

Output

484121060 448940322 484613337

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 18:13:15 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|