E. Яхуб и перестановки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Яхуб так обрадовался изобретению графов сортировки пузырьком, что он целый день сидит в офисе и выписывает перестановки. Яхубина вся извелась — ведь теперь Яхубу нет до нее дела. И вот, стоило Яхубу выйти, Яхубина зашла к нему в офис, чтобы саботировать его научную работу — и месть ее страшна.

Девушка отыскала важную для исследования Яхуба перестановку. Перестановка состояла из n различных целых чисел a1, a2, ..., an (1 ≤ ai ≤ n). Найдя перестановку, она сразу же заменила некоторые элементы перестановки числами -1.

Когда Яхуб вернулся, он обнаружил, что важная перестановка испорчена. Теперь Яхуб пытается ее восстановить. К сожалению, про изначальную перестановку он запомнил только то, что в перестановке не было ни одной неподвижной точки. Неподвижная точка перестановки — это такой элемент ak, значение которого равняется k (ak = k).

Ваша задача — доказать Яхубу, что восстанавливать перестановку уже не стоит. Выведите количество перестановок, которые могут оказаться изначальной важной перестановкой Яхуба по модулю 1000000007 (109 + 7).

Входные данные

В первой строке записано целое число n (2 ≤ n ≤ 2000). Во второй строке записано n целых чисел, описывающих важную перестановку Яхуба, после того, как Яхубина заменила некоторые значения на -1.

Гарантируется, что в заданной перестановке нет неподвижных точек. Также, гарантируется, что в заданной последовательности как минимум две -1 (минус единицы) и что никакое положительное число не встречается в перестановке более одного раза. Гарантируется, что при заданных ограничениях, существует хотя бы одна подходящая перестановка.

Выходные данные

Выведите единственное целое число — количество способов восстановления перестановки по модулю 1000000007 (109 + 7).

Примеры
Входные данные
5
-1 -1 4 3 -1
Выходные данные
2
Примечание

В первом тестовом примере две перестановки, не имеющие неподвижных точек: [2, 5, 4, 3, 1] и [5, 1, 4, 3, 2]. У всех остальных перестановок была бы по крайней мере одна неподвижная точка.