問題文

$N$ 枚のコインがあり、$1$ から $N$ の番号がついています。
これらのコインは特殊な形状をしているため、$i$ 番目のコインを無作為に投げたときに表が出る確率は $\displaystyle{\frac{P_i}{100}}$、裏が出る確率は $\displaystyle{\frac{100-P_i}{100}}$ です。

この中から $1$ 枚以上のコインを選び、AliceとBobが次のようなゲームをします。

• 選んだコインを全て無作為に投げる。
• 表が出たコインの枚数が奇数ならAliceの勝ちであり、偶数ならBobの勝ちである。

コインの選び方は $2^N-1$ 通りあります。そのうち、Aliceの勝つ確率が $1/2$ より真に大きくなるような選び方は何通りあるでしょうか。
答えは非常に大きくなることがあるので $10^9+7$ で割った余りを出力してください。

入力

$N$
$P_1\ \ P_2\ \ \cdots\ \ P_N$

• $1\le N\le 100$
• $0\le P_i \le 100$
• 入力は全て整数である。

出力

Aliceの勝つ確率が $1/2$ より真に大きくなるようなコインの選び方の数を $10^9+7$ で割った余りを出力してください。

サンプル

2
30 80

2

1
50

0