4525 - Stairs2 (Challenge)

• Submit
• Status
• Discuss
• Summary

Description

웰시씨는 계단을 오를 때 한 번에 한 칸이나 두 칸 오를 수 있다.

이 때, 계단 중에는 무조건 밟아야 하는 계단과 밟으면 안되는 계단이 섞여있다.

이 때, 웰시씨가 n개의 계단을 오르는 경우의 수는 총 몇 가지인가?

Input

* Line 1 : 입력의 갯수 N (1 ≤ N ≤ 1000)

* Line 2 ~ N+1 : 계단의 수 n과 각 계단의 상태가 공백으로 구분되어 한 줄로 입력된다. 이 때, 밟으면 안되는 계단은 -1, 일반 계단은 0, 밟아야 하는 계단은 1로 주어진다. (1 ≤ n ≤ 300)

Output

* Line 1~N : n개의 계단을 오르는 경우의 수를 출력한다. (단, 답은 2³² 미만이다.)

Sample Input

2
5 1 0 -1 1 0
4 0 0 0 0

Sample Output

1
5

Hint

5 1 0 -1 1 0은 아래 한 가지 경우밖에 없다.

 

계단을 오르는 방법의 수 = 맨 마지막에 한 칸 올라가는 방법의 수 + 맨 마지막에 두 칸 올라가는 방법의 수