問題文

イラストロジック・お絵かきロジック・ロジックパズル・ピクロスなどと呼ばれるパズルがあります（以降はロジックパズルと呼ぶことにします）。このパズルは、与えられる行・列ごとのヒントに応じてマス目を塗っていき、イラストを完成させるというものです。（詳しいルールはこちら）

ロジックパズルの行・列ごとのヒントはいくつかの非負整数からなり、それぞれの整数は「連続して塗るマスの数」を意味します。2つ以上の非負整数がある場合、それぞれの非負整数に対応して「連続して塗るマス」があり、順序が入れ替わったり、つながったりしてはいけません。

例えば、1行8マスのロジックパズルで、その行に7というヒントが与えられたとします。
この時、
■■■■■■■□
または
□■■■■■■■
の2通りの塗り方があります。

同じく、1行8マスのロジックパズルで2 4というヒントが与えられた場合
■■□■■■■□
■■□□■■■■
□■■□■■■■
という3通りの塗り方があります。2マス塗っている部分と4マス塗っている部分の間に必ず塗らないマスがあることと、左側が2マス、右側が4マスというように順番が入れ替わらないことに注意してください。

なお、複数個の数からなるヒントの場合、そのヒントの数の中に0は含まれません。0が使われるのは単独に限り、その場合は「その行を1マスも塗らない」という1通りの塗り方が存在します。

ロジックパズル研究者である貴方は、与えられる1行のヒントに対して、その行には何通りの塗り方があるのかを知りたいと考えました。1行のマスの数Mと、その行のヒントが与えられた時、ヒントを満たす塗り方が何通りあるか出力するプログラムを作成してください。答えの数はとても大きくなるので、1,000,000,007(=10⁹+7)で割った余りを出力してください。ただし、入力されたような塗り方が存在しない場合はNAと出力してください。

入力

M
H1 H2 H3 … Hk

入力の第1行には、ロジックパズルの1行のマスの数Mが1000000(=10⁶)以下の自然数で入力されます。
第2行には半角空白区切りで1行のヒントを示す非負整数列が与えられます。非負整数列の総和はMを超えず、ヒントの終端は改行で示されます。

出力

ヒントを満たす塗り方が何通りあるかを1,000,000,007で割った余りを1行で出力してください。出力の終端には改行を行ってください。

サンプル

10
7 1

3

12345
0

1

30
30

1

10
3 3 3

NA

654321
100 90 80 70 60 40 30 20 10 1 2 3 4 5 6 7 8 9 50

269216225