Hoán vị không điểm cố định

Cho một hoán vị bị thiếu của $n$ số nguyên phân biệt $a_1,a_2,\dots ,a_n$ (với $1\le a_i\le n$). Một số vị trí trong dãy đã bị thay bằng giá trị $-1$, biểu thị các phần tử bị mất.

Hoán vị gốc (trước khi bị xoá) không có điểm cố định, tức là không tồn tại chỉ số $k$ nào sao cho $a_k=k$.

Yêu cầu của bạn là đếm số cách khôi phục hoán vị gốc — nghĩa là điền lại các vị trí $-1$ bằng các giá trị còn thiếu sao cho dãy thu được là một hoán vị của $1,2,\dots ,n$ và không có điểm cố định nào. In kết quả modulo ${10}^9+7$.

Dữ liệu vào

• Dòng 1: số nguyên $n$.
• Dòng 2: $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($a_i=-1$ hoặc $1\le a_i\le n$). Đảm bảo trong dãy đã cho không có điểm cố định, có ít nhất hai giá trị $-1$, và mỗi giá trị dương xuất hiện không quá một lần. Đảm bảo luôn tồn tại ít nhất một cách khôi phục hợp lệ.

Dữ liệu ra

Một số nguyên duy nhất — số cách khôi phục hoán vị gốc, lấy modulo ${10}^9+7$.

Ràng buộc

• $2\le n\le 2000$.

Ví dụ