Count IS for All Subsets

2 secs 1024 MB
bayashiko

問題文


長さ の整数列 が与えられます。
集合 の空でない部分集合 に対して、 を以下のように定義します。

  • の空でない部分集合 であって、 となるようなものの個数

として考えられるものは全部で 通りありますが、そのすべてに対する の和を で割った余りを求めてください。

  

制約


  • 入力は全て整数   

入力


入力は以下の形式で標準入力から与えられます。


  

出力


答えを出力してください。

  

入力例1


3
1 3 2

出力例1


16








と計算できるので答えは です。

入力例2


16
8 4 11 2 6 11 9 1 2 1 10 10 7 8 13 1

出力例2


2197504

Submit


Go (1.14)