올레그와 이진 수열

올레그는 0과 1로 이루어진 이진 수열을 아주 좋아한다. 얼마 전 그는 공책에 $n$개의 원소로 이루어진 이진 수열을 하나 적었다. 올레그는 적은 수열에 대해 Z-함수를 계산했다.

수열 $s_1, \ldots, s_n$의 Z-함수란 배열 $z[1..n]$이며, 다음과 같이 정의된다.

• $z[1] = 0$;
• $i > 1$일 때, $z[i]$는 수열 $s$와 $i$번째 위치에서 시작하는 $s$의 접미사의 최장 공통 접두사의 길이이다. 다시 말해 $z[i]$는 $s_1 = s_i$, $s_2 = s_{i+1}$, ..., $s_{k} = s_{i+k-1}$을 만족하는 최대 $k$이다.

예를 들어 수열 $s = \langle 0, 0, 1, 1, 0, 0, 1 \rangle$의 Z-함수는 $z = \langle 0, 1, 0, 0, 3, 1, 0\rangle$이다.

공책에 수열과 그 Z-함수를 적은 올레그는 잠이 들었다. 그가 자는 동안 남동생 예고르가 방에 몰래 들어와 수열과 Z-함수의 일부 값을 형광펜으로 지웠다. 잠에서 깬 올레그는, 지워지지 않고 남은 Z-함수의 값이 올바르게 되는 그러한 이진 수열을 그가 저녁에 몇 개나 공책에 적었을 수 있는지 궁금해졌다.

조건을 만족하는 수열의 개수를 구해 $10^9 + 7$로 나눈 나머지를 출력하라. 올레그가 Z-함수를 계산할 때 실수했을 수도 있으며, 이 경우에는 어떤 수열도 조건을 만족하지 않으므로 답은 0이다.

첫째 줄에 원래 이진 수열의 길이 $n$이 주어진다 ($1 \le n \le 1000$). 둘째 줄에 $n$개의 정수 $z[1], \ldots, z[n]$이 주어지며, $z[i]$는 $i$번째 위치의 Z-함수 값이고, $i$번째 위치의 값이 지워졌다면 $-1$이다 ($-1 \le z[i] \le n$).

조건을 만족하는 이진 수열의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

첫 번째 예제에서는 수열 $\langle 0, 1, 0 \rangle$과 $\langle 1, 0, 1 \rangle$이 조건을 만족한다.

두 번째 예제에서는 주어진 Z-함수를 갖는 길이 4의 이진 수열이 존재하지 않는다.

세 번째 예제에서는 $z[2] = 3$이며, 이는 Z-함수의 정의에 어긋나므로 답은 0이다.

네 번째 예제에서는 길이 3의 모든 이진 수열이 조건을 만족한다.