AT_arc164_d [ARC164D] 1D Coulomb

[problemUrl]: https://atcoder.jp/contests/arc164/tasks/arc164_d 長さ $ 2N $ で `+` , `-` が $ N $ 個ずつからなる文字列 $ s $ に対して次の問題を考え、その答えを $ p(s) $ と書くことにします。 > 数直線上の $ x=1,2,3,\ldots\ ,\ 2N $ の位置に $ 2N $ 個のボールが並んでおり、そのうち $ N $ 個は $ +1 $ の、残りの $ N $ 個は $ -1 $ の電荷を持ちます。ボールの持つ電荷の並び方は $ s $ によって表され、$ s $ の $ i $ 文字目が `+` であれば $ x=i $ には $ +1 $ の電荷を持つボールが、`-` であれば $ x=i $ には $ -1 $ の電荷を持つボールが配置されていることを表します。 > > それぞれのボールは、次の規則にしたがって、一斉に運動を始めます。ただし、数直線上でより小さい数が位置する方向を左、より大きい数が位置する方向を右と呼びます。 > > - 各ボールに対して、各時点で $ F $ を次の式で定める > $ F=\lbrace $ $ ( $自身より真に左に存在するボールの電荷の総和$ ) $ $ - $ $ ( $自身より真に右に存在するボールの電荷の総和$ ) $ $ \rbrace $ $ \times $ $ ( $自身の電荷$ ) $ > - 各ボールは各時点で、$ F $ が正であれば右に、負であれば左に、毎秒 $ 1 $ の速さで動く > - 同時に同じ座標に電荷 $ +1 $ のボールと電荷 $ -1 $ のボールが存在した場合、両者は打ち消しあって消滅する > > このとき、それぞれのボールが運動を始めてから消滅するまでに移動した距離（消滅した座標と初めの座標の差の絶対値）の総和はいくつでしょうか。 長さ $ 2N $ で、`+` , `-` , `?` からなる文字列 $ T $ が与えられます。$ T $ の `?` を `+` または `-` に置換することで得られる、 `+` , `-` が $ N $ 個ずつからなる文字列 $ s $ 全てについての $ p(s) $ の総和を $ 998244353 $ で割った余りを求めてください。 なお、与えられた制約と運動の規則の下で、有限の時間内に全てのボールが消滅すること、ボールが消滅しない限り各ボールの $ F $ の値が $ 0 $ にならないこと、$ 3 $ つ以上のボールが同時に同じ座標に位置する瞬間が無いこと、および $ p(s) $ が整数になることが示せます。

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

答えを $ 998244353 $ で割った余りを整数で出力せよ。

### 制約 - $ 1\leq\ N\leq\ 3000 $ - $ N $ は整数である - $ |T|=2N $ - $ T $ の各文字は `+` , `-` , `?` のいずれかであり、 `+` と `-` はそれぞれ $ N $ 個以下である ### Sample Explanation 1 $ T $ から得られる文字列 $ s $ として、 `++--` と `+-+-` が考えられます。 `++--` について、運動を開始した時点では各ボールの左右の電荷の総和、および $ F $ の値は次のようになります。 !\[\](https://img.atcoder.jp/arc164/403850a82c3adfb838197734344ae193.png) したがって、$ x=1,2 $ のボールは右に、$ x=3,4 $ のボールは左に動き始めます。 この場合、各ボールはその後運動の向きを変えることなく、 $ 0.5 $ 秒後に $ x=2,3 $ にあったボールが $ x=2.5 $ で、$ 1.5 $ 秒後に $ x=1,4 $ にあったボールが $ x=2.5 $ でそれぞれ消滅します。 この間に、$ x=2,3 $ にあったボールは $ 0.5 $ ずつ、$ x=1,4 $ にあったボールは $ 1.5 $ ずつの距離を移動しているため、$ p( $ `++--` $ )=4 $ です。 同様に観察すると $ p( $ `+-+-` $ )=2 $ であることが分かるため、求める $ p(s) $ の総和は $ 6 $ となります。 ### Sample Explanation 2 $ p(s) $ の総和を $ 998244353 $ で割った余りを出力してください。