AT_jsc2026_final_e Ensmile

`:`、`|` のみからなる文字列 $ S $ が与えられます。 $ S $ に含まれる `|` の個数を $ m $ とします。 $ k = 0,1,\ldots,m $ について、 $ S $ に含まれる `|` のうち左から $ k $ 個を `)` に、残りの $ m-k $ 個を `(` に置き換えた文字列を $ s_k $ とします。 $ t = s_0,s_1, \ldots, s_m $ について、以下の問題を解いてください。 > 以下のいずれかの操作を行うことを、いずれの操作も行えなくなるまで繰り返します。 > > - $ t $ の部分文字列 `):` を $ 1 $ つ選び、`:)` に置き換える。 > - $ t $ の部分文字列 `:(` を $ 1 $ つ選び、`(:` に置き換える。 > > このとき、あり得る操作列の個数を $ 998244353 $ で割った余りを求めてください。 > > ただし、各操作後に得られる文字列の列によって操作列を区別するものとします。

入力は以下の形式で標準入力から与えられる。 > $ S $

$ t = s_0,s_1, \ldots, s_m $ に対する答えをこの順に空白区切りで出力せよ。

### Sample Explanation 1 例えば $ s_1 $ は `:):(:(:` であり、 $ t=s_1 $ のときあり得る操作列は以下の $ 4 $ 個です。 - `:):(:(:` $ \to $ `::)(:(:` $ \to $ `::)((::` - `:):(:(:` $ \to $ `:)(::(:` $ \to $ `:)(:(::` $ \to $ `:)((:::` - `:):(:(:` $ \to $ `:):((::` $ \to $ `::)((::` - `:):(:(:` $ \to $ `:):((::` $ \to $ `:)(:(::` $ \to $ `:)((:::` ### Constraints - $ 2 \le |S| \le 5000 $ - $ S $ は `:`、`|` のみからなる - $ S $ は `|` を $ 1 $ つ以上含む