Олег и двоичные последовательности

Олег очень любит двоичные последовательности --- последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из $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$.

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

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

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

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