Binary-Search Game

2 secs 1024 MB
riano_

問題文


から までの番号が付いた 枚のコインがあり、この中に 枚だけ偽物が混じっていることがわかっています。 あなたは、はじめ 円持っており、 円を支払うことで、支払いが可能である限り何度でも、

  • 以下の番号のコインに偽物が含まれていますか」

と尋ねることができます。 ここで、 は質問の度に毎回自由に選ぶことができ、また、この質問に対しては常に正しい答えが返ってくることが保証されます。 (なお、コインは日本円ではないため 枚のコインの一部を支払いに利用することはできません。) そして、最後に一度だけ「何番のコインが偽物であるか」を宣言することができます。 この宣言が的中していた場合、あなたの勝利となります。

どのコインも偽物である確率が等しい(すなわち、どのコインも の確率で偽物である)と仮定したとき、あなたが最適な質問順と宣言を選ぶと勝利できる確率はいくらでしょうか。

この答えは有理数であることが証明できますので、 で答えてください。 厳密には、答えを既約分数で としたとき、 となる、 以上 未満の整数 を答えてください。

制約


  • 入力は全て整数である

入力


出力


上述の の値を出力してください。

サンプル


入力1
3 2
出力1
665496236

あなたは 円持っているため、例えば として「 番以下に偽物があるか」を尋ねることができます。

答えがいいえであれば、 番が確実に偽物です。 このようになる確率は、条件より であり、この場合は確実に勝利できます。

答えがはいであれば、 番または 番が偽物です。 このときあなたは所持金を使い切ってしまっているため、これ以上の質問はできません。 このようになる確率は であり、あなたはどちらかを当てずっぽうに選んで宣言することで、この状況から の確率で勝利できます。 したがって、 番または 番が偽物であり、かつ偶然にも勝利できる確率は となります。

以上より、あなたの勝率は となるので、 では上記の答えになります。

入力2
2 0
出力2
499122177

質問はできませんが、当てずっぽうな宣言で の勝率が得られます。

入力3
5 7
出力3
1

あなたは最適な順で質問することで、確実に偽物を特定し、勝利することができます。

提出


Go (1.14)