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$ で割ったあまりを求めてください。