問題文

$1$ 以上 $T$ 以下の整数を、各 $i$ は $0$ 個以上 $a_{i}$ 個以下の範囲で、好きな個数黒板に書くことができます。

書かれている整数に対して次の操作を繰り返して、ただ $1$ つの整数が黒板に書かれているようにできるような整数の書き方は何通りあるでしょうか。

• 黒板に書かれている整数のうち、$2$ つ以上ある整数 $X$ を $2$ つ消して、黒板に $X+1$ を $1$ つ書く

答えは非常に大きくなることがあるので、$1000000007$ で割った余りを計算してください。

ただし $2$ つの書き方が異なるとは、それぞれの書き方において操作を始める前に黒板に書かれている個数が異なるような整数が存在する場合を表します。

制約

• $1 \\leq T \\leq 300$
• $0 \\leq a_i \\leq 300$
• 入力は全て整数である

入力

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

$T$ $a_1$ $a_2$ ... $a_{T-1}$ $a_T$

出力

上手く操作を行うことで黒板に書かれている整数を $1$ つに出来るような選び方の個数を $1000000007$ で割った余りを出力せよ。

入力例 1

2
1 1

出力例 1

2

$1$ を $1$ つ書くか、$2$ を $1$ つ書く方法が条件を満たします。

入力例 2

3
2 1 1

出力例 2

6

入力例 3

8
300 300 300 300 300 300 300 300

出力例 3

220439161