問題文


ある村には人の人間と匹の人狼がいることが分かっています.

人狼の数が人間の数以上になると,その瞬間に全ての人間は人狼に食べられてしまいます.

これから村では「(生存している)人間が人になる」か「(生存している)人狼が匹になる」まで以下の事件が交互に繰り返されます.

  1. 襲撃が起こり,人間が一人食べられる.

  2. 処刑が起こり,人間または人狼が一人(一匹)減る. 処刑対象は生存している人間または人狼から無作為に選ばれる.

事件が起こらなくなった時点で生存している人間の数の期待値を求め,で出力してください.

より正確には,期待値が有理数,つまりある既約分数で表されること,さらにを満たす整数が一意に定まることがこの問題の制約より証明できます.よって,このを出力してください.

制約


  • 入力は全て整数

入力


入力はすべて整数である.

出力


期待値をで出力せよ.

サンプル


入力1
3 1
出力1
665496236

以下のように人数が変化します.

まず襲撃が起こり,人間は人,人狼は匹になります.

次の処刑では,

  • の確率で人狼が処刑され,事件が起こらなくなります.生存している人間は人です.
  • の確率で人間が処刑され,人間と人狼が同数になって全ての人間が食べられ,事件が起こらなくなります.生存している人間は人です.

したがって,生存している人間の数の期待値はです.で出力することに注意してください.

入力2
3 3
出力2
0
入力3
1999 1
出力3
666

提出


Go (1.14)