#agc021e. [agc021_e]Ball Eat Chameleons
[agc021_e]Ball Eat Chameleons
問題文
AtCoder 共和国では、カメレオン科ボールタベルカメレオン属に属するスヌケカメレオンがペットとして大人気です。 りんごさんは、 匹のスヌケカメレオンの個体をひとつのカゴに入れて飼っています。
何も食べていない状態のスヌケカメレオンは青色です。スヌケカメレオンは、次の規則で変色します。
- 青いスヌケカメレオンは、これまでに食べた青いボールの個数よりこれまでに食べた赤いボールの個数の方が真に大きくなった時、赤色に変色する。
- 赤いスヌケカメレオンは、これまでに食べた赤いボールの個数よりこれまでに食べた青いボールの個数の方が真に大きくなった時、青色に変色する。
最初、スヌケカメレオンたちはどの個体も何も食べていない状態です。りんごさんは、スヌケカメレオンたちに、以下の手順を 回繰り返すことで餌をやりました。
- 赤いボールまたは青いボールを握る。
- 握ったボールを、スヌケカメレオンたちの入ったカゴの中に投げ入れる。このとき、いずれか一匹がそのボールを食べる。
りんごさんが 個のボールを投げ入れたところ、全ての個体が赤色になっていました。りんごさんの 個のボールの投げ入れ方としてありうるものは何通りあるでしょうか。 で割った余りを求めてください。ただし、 つの投げ入れ方が異なるとは、ある が存在し、 個目に投げ入れたボールの色が異なることを指します。
制約
- は整数である
入力
入力は以下の形式で標準入力から与えられる。
出力
個のボールの投げ入れ方としてありうるものの個数を で割った余りを出力せよ。
入力例 1
2 4
出力例 1
7
個目に投げ入れるボールが赤のとき R
を、青のとき B
を順に並べた文字列を用いて投げ入れ方を表せば、 BRRR
,RBRB
,RBRR
,RRBB
,RRBR
,RRRB
,RRRR
の 個が条件を満たします。
入力例 2
3 7
出力例 2
57
入力例 3
8 3
出力例 3
0
入力例 4
8 10
出力例 4
46
入力例 5
123456 234567
出力例 5
857617983