Thiết kế hệ thống đèn

Để trang trí hội trường cho buổi khai mạc Duyên Hải năm 2022, Ban tổ chức đã sử dụng $n$ đèn, nếu coi mỗi đèn là một đỉnh của đồ thị và dây nối giữa các đèn là cạnh thì hệ thống đèn tương ứng như một cây. Ban tổ chức đã ghi chép lại dãy các thông tin $b_1,b_2,\dots ,b_n$, trong đó $b_i$ ($1\le i\le n$) tương ứng là số dây nối với đèn thứ $i$, hay nói một cách khác $b_i$ là bậc của đỉnh $i$. Vì một lí do nào đó, Ban tổ chức đã vô tình làm mất thông tin của một số phần tử trong dãy thông tin $b_1,b_2,\dots ,b_n$. Để khôi phục lại các thông tin, Ban tổ chức đã nhờ đến Đào Quang Thái Dương (là cựu học sinh Chuyên Trần Phú, Huy chương Đồng APIO 2020). Rất nhanh chóng, Dương đã đếm được số lượng cách khác nhau điền thông tin vào các phần tử bị khuyết để nhận được dãy vẫn là dãy bậc của một cây nào đó.

Dãy $d_1,d_2,\dots ,d_n$ là dãy bậc của một cây nếu tồn tại một cây gồm $n$ đỉnh đánh số từ $1$ đến $n$ mà đỉnh $i$ có bậc đúng bằng $d_i$ với mọi $i$. Hai cách điền được coi là khác nhau nếu có ít nhất một vị trí bị khuyết được điền hai giá trị khác nhau. Nếu không có phần tử nào bị khuyết thì có $1$ cách điền (không điền gì) khi dãy đã cho là dãy bậc của một cây, ngược lại có $0$ cách.

Yêu cầu: Gọi $s$ là số lượng cách điền thỏa mãn, hãy tính $smod({10}^9+7)$.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương $n$;
• Dòng thứ hai chứa $n$ số nguyên $b_1,b_2,\dots ,b_n$, trong đó $1\le b_i\le n-1$ hoặc $b_i=-1$ cho biết thông tin đỉnh $i$ bị mất.

Dữ liệu ra

In ra một số nguyên là giá trị $smod({10}^9+7)$.

Ràng buộc

• $2\le n\le {10}^6$.
• $1\le b_i\le n-1$ hoặc $b_i=-1$.

Subtasks

Điểm được tính theo từng test.

• Có $20\%$ số lượng test ứng với $20\%$ số điểm thỏa mãn: $n\le 6$.
• Có $20\%$ số lượng test khác ứng với $20\%$ số điểm thỏa mãn: $n\le 10$.
• Có $20\%$ số lượng test khác ứng với $20\%$ số điểm thỏa mãn: $n\le 100$.
• Có $20\%$ số lượng test khác ứng với $20\%$ số điểm thỏa mãn: $n\le {10}^4$.
• Có $20\%$ số lượng test còn lại ứng với $20\%$ số điểm thỏa mãn: $n\le {10}^6$.

Ví dụ