Time Limit: 1s
Memory Limit: 128MB
피크로스 퍼즐은 각 줄마다 연속으로 칠해진 칸 수가 주어져서, 이를 통해 전체 그림을 알아내는 퍼즐이다.
예를 들어, 어떤 줄에 2 3이 주어졌다면 그 줄은 연속으로 2칸이 칠해져 있고, 그 다음에 공백이 1칸이상 있으며, 연속으로 3칸 칠해져 있다는 것을 의미한다.
가로 6칸짜리 로직퍼즐에서 어떤 가로줄에 2 3이 주어졌다면 그 줄은
위와 같이 칠해지는 경우 한 가지 밖에 없을 것이다.
피크로스퍼즐 중 한 줄이 주어졌을 때, 주어진 줄을 칠하는 경우의 수를 구해보자.
Line 1: 전체 칸 수 n (1 ≤ n ≤ 100)
Line 2: 연속으로 칠해진 칸의 갯수 N (1 ≤ N ≤ 10)
Line 3: N개의 연속으로 칠해진 칸 a가 공백으로 구분되어 한 줄로 입력된다. (1 ≤ a ≤ 10)
Line 1: 가능한 경우의 수를 출력한다.
15 3 5 3 1
35
15개의 칸에 연속으로 5칸, 3칸, 1칸을 칠하는 방법은 다음과 같다. (칠한 칸: 1, 빈칸: 0)
1 1 1 1 1 0 1 1 1 0 1 0 0 0 0
1 1 1 1 1 0 1 1 1 0 0 1 0 0 0
1 1 1 1 1 0 1 1 1 0 0 0 1 0 0
1 1 1 1 1 0 1 1 1 0 0 0 0 1 0
1 1 1 1 1 0 1 1 1 0 0 0 0 0 1
1 1 1 1 1 0 0 1 1 1 0 1 0 0 0
1 1 1 1 1 0 0 1 1 1 0 0 1 0 0
1 1 1 1 1 0 0 1 1 1 0 0 0 1 0
1 1 1 1 1 0 0 1 1 1 0 0 0 0 1
1 1 1 1 1 0 0 0 1 1 1 0 1 0 0
1 1 1 1 1 0 0 0 1 1 1 0 0 1 0
1 1 1 1 1 0 0 0 1 1 1 0 0 0 1
1 1 1 1 1 0 0 0 0 1 1 1 0 1 0
1 1 1 1 1 0 0 0 0 1 1 1 0 0 1
1 1 1 1 1 0 0 0 0 0 1 1 1 0 1
0 1 1 1 1 1 0 1 1 1 0 1 0 0 0
0 1 1 1 1 1 0 1 1 1 0 0 1 0 0
0 1 1 1 1 1 0 1 1 1 0 0 0 1 0
0 1 1 1 1 1 0 1 1 1 0 0 0 0 1
0 1 1 1 1 1 0 0 1 1 1 0 1 0 0
0 1 1 1 1 1 0 0 1 1 1 0 0 1 0
0 1 1 1 1 1 0 0 1 1 1 0 0 0 1
0 1 1 1 1 1 0 0 0 1 1 1 0 1 0
0 1 1 1 1 1 0 0 0 1 1 1 0 0 1
0 1 1 1 1 1 0 0 0 0 1 1 1 0 1
0 0 1 1 1 1 1 0 1 1 1 0 1 0 0
0 0 1 1 1 1 1 0 1 1 1 0 0 1 0
0 0 1 1 1 1 1 0 1 1 1 0 0 0 1
0 0 1 1 1 1 1 0 0 1 1 1 0 1 0
0 0 1 1 1 1 1 0 0 1 1 1 0 0 1
0 0 1 1 1 1 1 0 0 0 1 1 1 0 1
0 0 0 1 1 1 1 1 0 1 1 1 0 1 0
0 0 0 1 1 1 1 1 0 1 1 1 0 0 1
0 0 0 1 1 1 1 1 0 0 1 1 1 0 1
0 0 0 0 1 1 1 1 1 0 1 1 1 0 1