みそ君は, 個の部分からなる横に細長い1本のチョコレートをもらいました。
チョコレートのそれぞれの部分の固さは, で表されます。
また,チョコレートのそれぞれの部分の境目には切れ込みが入っています。
みそ君は,このチョコレートをある特殊な機械に入れ,いくつかの塊に分割しようと思いました。
その特殊な機械では,どの切れ込みに対しても の確率で,その切れ込みでチョコレートを分割するように動作します。
そうして,いくつかの塊に分割されたチョコレートの美味しさを次のように定義します。
例として, , , であるチョコレートを, に分割したとすると, となり,この分割の仕方での美味しさは となります。
最終的に得られる美味しさの期待値(これは有理数になります。)を,注記で述べるように で求めてください。
有理数を出力する際は、まずその有理数を分数 で表してください。
ここで, は整数であり, は で割り切れてはいけません。
そして, となる 以上 以下の整数 を出力してください。
最終的に得られる美味しさの期待値を1行に出力してください。
3 3 1 4
7
分割の仕方は, と と と の 通りあり,それぞれの美味しさは です。よって,求める期待値は となります。
3 9 9 7
500000019
求める期待値は となりますが,出力すべき値は, を満たす整数 で,この値は となります。