問題一覧 > 通常問題

No.389 Combinations of a Logic Puzzle

レベル : / AI推定難易度 : 700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 146
作問者 : tatuyan_edson / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 1030 / 自分の提出
問題文最終更新日: 2026-06-25 07:59:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 141 (順位表) の他の問題:

Problem Statement


There is a type of puzzle known as Illustration Logic, Oekaki Logic, Logic Puzzle, Picross, and so on (hereafter called a logic puzzle). In this puzzle, you complete an illustration by painting cells according to the hints given for each row and column. (Detailed rules are here.)

The hint for each row or column of a logic puzzle consists of several non-negative integers, and each integer means "the number of consecutive cells to paint". When there are two or more non-negative integers, each one has its own corresponding "run of consecutively painted cells", and these runs must not change order or join together.

For example, suppose that in a logic puzzle with 8 cells in a row, the hint 7 is given for that row.
In this case, there are 2 ways to paint:
■■■■■■■□
or
□■■■■■■■
.

Similarly, if the hint 2 4 is given in a logic puzzle with 8 cells in a row, there are 3 ways to paint:
■■□■■■■□
■■□□■■■■
□■■□■■■■
Note that there must always be an unpainted cell between the 2-cell painted part and the 4-cell painted part, and that the order must not be swapped: the 2 cells are on the left and the 4 cells are on the right.

A hint consisting of multiple numbers does not contain 0. 0 is used only on its own, and in that case there is exactly 1 way to paint: "paint no cell in that row".

You, a logic puzzle researcher, want to know how many ways there are to paint a row for a given hint of that row. Write a program that, given the number of cells M in a row and the hint for that row, outputs the number of ways to paint that satisfy the hint. Since the answer can be very large, output the remainder when divided by 1,000,000,007(=109+7). However, if no way of painting as given in the input exists, output NA.

Input

M
H1 H2 H3 … Hk


The first line of the input contains the number of cells M in a row of the logic puzzle, a natural number not exceeding 1000000(=106).
The second line contains a sequence of non-negative integers separated by single-byte spaces, representing the hint for the row. The sum of the sequence does not exceed M, and the end of the hint is indicated by a newline.

Output


Output on one line the number of ways to paint that satisfy the hint, modulo 1,000,000,007. Print a newline at the end of the output.

Sample

Sample 1
Input
10
7 1
Output
3


The following 3 ways are possible.
■■■■■■■□■□
■■■■■■■□□■
□■■■■■■■□■

Sample 2
Input
12345
0
Output
1


When the hint is 0, there is only 1 way to paint: "paint nothing".

Sample 3
Input
30
30
Output
1


The only possibility is 1 way: "paint everything".

Sample 4
Input
10
3 3 3
Output
NA


The hint 3 3 3 cannot be painted in 10 cells.

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


提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。