筑波大学プログラミングコンテスト2023
コンテスト日時
2023/09/03 (Su) 14:00 - 17:00

D - Line Up Alternately

Earlgray
2
s
1024
MB
400

問題文

モンスターブリーダーのえぬ君は赤と青の $2$ 種類のスライムを飼っています。
赤のスライムは $X$ 匹、青のスライムは $Y$ 匹で、青のスライムは赤のスライムより若干多いです。
えぬ君はこの $(X+Y)$ 匹のスライムをこれから一列に並べます。
ただし、同じ色のスライムを $3$ 匹連続で並べるとそれらは合体し、えぬ君に襲いかかってきてしまうため、同じ色のスライムは $3$ 匹以上連続しないようにする必要があります。
この条件のもと、 $(X+Y)$ 匹のスライムを一列に並べる方法の数を $998244353$ で割ったあまりを求めてください。
スライムにはえぬ君によって相異なる名前がつけられているので、すべてのスライムを区別します。

制約

  • 入力はすべて整数
  • $1 \le X < Y \le \min (2(X+1),5\times 10^{5})$

入力

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

$X$ $Y$

出力

答えを $998244353$ で割ったあまりを一行に出力せよ。

入力例 1
1 2
出力例 1
6

$3$ 匹のスライムを並べる方法は $6$ 通りあり、いずれも条件を満たします。

入力例 2
3 4
出力例 2
2592

例えば、次の図の上のような順(青、赤、青、青、赤、青、赤)に並べることはできますが、下のような順(青、赤、 青、青、青、 赤、赤)で並べることはできません。

並べ方の解説

すべてのスライムを区別するとき、同色のスライムが $3$ 匹以上連続しないような並べかたは全部で $2592$ 通りです。

入力例 3
100 120
出力例 3
40810404

答えを $998244353$ で割ったあまりを求めてください。

提出
C++23 (g++ 12.2.0)