Задача №111974. Олег и двоичные последовательности
Олег очень любит двоичные последовательности - последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из \(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}\), ... , \(s_{k} = s_{i+k-1}\).
Записав в тетради последовательность и ее 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.
3 0 0 1
2
4 0 0 1 0
0
3 0 3 -1
0
3 -1 -1 -1
8