시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
Олег очень любит двоичные последовательности --- последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из $n$ элементов. Для выписанной последовательности Олег посчитал Z-функцию.
Z-функцией последовательности $s_1, \ldots, s_n$ называется массив $z[1..n]$, в котором:
Например, для последовательности $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$.
3 0 0 1
2
4 0 0 1 0
0
3 0 3 -1
0
3 -1 -1 -1
8
В первом примере подходят последовательности $\langle 0, 1, 0 \rangle$ и $\langle 1, 0, 1 \rangle$.
Во втором примере не существует ни одной двоичной последовательности длины 4 с заданной Z-функцией.
В третьем примере $z[2] = 3$, что противоречит определению Z-функции, поэтому ответ 0.
В четвертом примере подходит любая двоичная последовательность длины 3.