시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB0000.000%

문제

Олег очень любит двоичные последовательности --- последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из $n$ элементов. Для выписанной последовательности Олег посчитал Z-функцию.

Z-функцией последовательности $s_1, \ldots, s_n$ называется массив $z[1..n]$, в котором:

  • $z[1] = 0$;
  • Если $i > 1$, то $z[i]$ равно длине наибольшего общего префикса последовательности $s$ и суффикса последовательности $s$, начинающегося с $i$-й позиции. Иначе говоря, $z[i]$ равно максимальному $k$, такому что $s_1 = s_i$, $s_2 = s_{i+1}$, \dots, $s_{k} = s_{i+k-1}$.

Например, для последовательности $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]$ --- значение Z-функции в позиции $i$, или $-1$, если значение в $i$-й позиции было закрашено ($-1 \le z[i] \le n$).

출력

В выходной файл выведите единственное число --- остаток от деления числа подходящих двоичных последовательностей на число $10^9 + 7$.

예제 입력 1

3
0 0 1

예제 출력 1

2

예제 입력 2

4
0 0 1 0

예제 출력 2

0

예제 입력 3

3
0 3 -1

예제 출력 3

0

예제 입력 4

3
-1 -1 -1

예제 출력 4

8

힌트

В первом примере подходят последовательности $\langle 0, 1, 0 \rangle$ и $\langle 1, 0, 1 \rangle$.

Во втором примере не существует ни одной двоичной последовательности длины 4 с заданной Z-функцией.

В третьем примере $z[2] = 3$, что противоречит определению Z-функции, поэтому ответ 0.

В четвертом примере подходит любая двоичная последовательность длины 3.