Random Xor Division

2 secs 1024 MB
OxOmiso

問題文


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

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

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

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

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

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

注記


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

制約



入力



出力


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

入力例 1


3
3 1 4

出力例 1


7

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

入力例 2


3
9 9 7

出力例 2


500000019

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

Submit


Go (1.14)