Để 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},…,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},…,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 đó.

Yêu cầu: Gọi s là số lượng cách điền thỏa mãn, hãy tính \(s\) % \((10^{9}+7)\), trong đó % là phép chia lấy dư để kiểm tra kết quả của Dương.

Input

• 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},…,b_{n}\), trong đó \(1 \leq b_{i} \leq n-1\) hoặc \(b_{i}=-1\) cho biết thông tin đỉnh \(i\) bị mất.

Output

• In ra một số nguyên là giá trị \(s \% (10^9+7)\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n\le 6\);
• Subtask \(2\) (\(20\%\) số điểm): \(n\le 10\);
• Subtask \(3\) (\(20\%\) số điểm): \(n\le 100\);
• Subtask \(4\) (\(20\%\) số điểm): \(n\le 10^{4}\);
• Subtask \(5\) (\(20\%\) số điểm): \(n\le 10^{6}\).

Example

3
-1 -1 1

2