Random Xor Division

みそ君は， 個の部分からなる横に細長い1本のチョコレートをもらいました。
チョコレートのそれぞれの部分の固さは， で表されます。
また，チョコレートのそれぞれの部分の境目には切れ込みが入っています。
みそ君は，このチョコレートをある特殊な機械に入れ，いくつかの塊に分割しようと思いました。

その特殊な機械では，どの切れ込みに対しても の確率で，その切れ込みでチョコレートを分割するように動作します。

そうして，いくつかの塊に分割されたチョコレートの美味しさを次のように定義します。

• 美味しさは，各塊に含まれる部分の固さの をとった値の総和 である。

例として， , , であるチョコレートを， に分割したとすると， となり，この分割の仕方での美味しさは となります。

最終的に得られる美味しさの期待値（これは有理数になります。）を，注記で述べるように で求めてください。

有理数を出力する際は、まずその有理数を分数 で表してください。
ここで， は整数であり， は で割り切れてはいけません。
そして， となる 以上 以下の整数 を出力してください。

最終的に得られる美味しさの期待値を1行に出力してください。

3
3 1 4

7

分割の仕方は， と と と の 通りあり，それぞれの美味しさは です。よって，求める期待値は となります。

3
9 9 7

500000019

求める期待値は となりますが，出力すべき値は， を満たす整数 で，この値は となります。