BTtown bao gồm $n$ ngôi nhà, được đánh số từ $1$ đến $n$. Vị trí các ngôi nhà được mô tả bằng một hoán vị $p_1, \dots, p_n$: ngôi nhà $i$ và $p_i$ được coi là hàng xóm của nhau. Nếu $p_i = i$, điều đó có nghĩa là ngôi nhà thứ $i$ không có hàng xóm.

Các vấn đề kỹ thuật tại trạm điện trung tâm của thành phố buộc chính quyền phải cắt điện các ngôi nhà khỏi lưới điện từng ngôi nhà một. Giả sử thứ tự cắt điện được mô tả bởi hoán vị $q_1, \dots, q_n$. Ban đầu, mọi ngôi nhà đều được kết nối với lưới điện. Trong ngày thứ $i$, ngôi nhà mang số hiệu $q_i$ sẽ bị ngắt khỏi lưới điện.

Để giảm bớt khó khăn, người dân có nghĩa vụ giúp đỡ những người hàng xóm đang gặp khó khăn: cư dân của những ngôi nhà vẫn còn kết nối với lưới điện sẽ cần kéo cáp đến những ngôi nhà hàng xóm đã bị ngắt khỏi lưới điện. Cần lưu ý rằng việc này sẽ KHÔNG dẫn đến việc kết nối lại ngôi nhà hàng xóm vào lưới điện.

Tại bất kỳ thời điểm nào, các điều kiện sau sẽ luôn đúng: Một sợi cáp chạy giữa hai ngôi nhà khi và chỉ khi chúng là hàng xóm của nhau và chỉ một trong hai ngôi nhà đó được kết nối với lưới điện. Do đó, nếu cả hai ngôi nhà đều đã bị ngắt khỏi lưới điện, các sợi cáp có thể đã chạy giữa hai ngôi nhà trước đó sẽ bị loại bỏ.

Vào cuối mỗi ngày, thành phố sẽ được chia thành các nhóm nhà kết nối với nhau bằng các sợi cáp do người dân tự kéo. Để phân tích sự ổn định của lưới điện, việc theo dõi số lượng các nhóm như vậy là rất quan trọng. Độ bất ổn (instability) của thứ tự cắt điện $q$ là tổng số lượng các nhóm như vậy qua mỗi ngày trong số $n$ ngày.

Chính quyền thành phố vẫn chưa quyết định thứ tự $q$ và cần phải tìm tổng độ bất ổn trên tất cả các thứ tự có thể. Hãy giúp thành phố tính toán giá trị này theo modulo $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^6$). Dòng thứ hai chứa $n$ số nguyên cách nhau bởi dấu cách $p_1, \dots, p_n$ ($1 \le p_i \le n$, $p_i \neq p_j$ nếu $i \neq j$).

Dữ liệu ra

In ra một số nguyên duy nhất – phần dư của phép chia tổng độ bất ổn trên tất cả các thứ tự cắt điện có thể cho $10^9 + 7$.

Scoring

Bài toán này bao gồm 7 nhiệm vụ con, đáp ứng các yêu cầu sau:

1. $n \le 8$. Trị giá 8 điểm.
2. $n \le 18$. Trị giá 10 điểm.
3. $n \le 30$. Trị giá 13 điểm.
4. $n \le 2000$. Trị giá 22 điểm.
5. $n \le 100000$, $p_i = n - i + 1$. Trị giá 16 điểm.
6. $n \le 100000$. Trị giá 12 điểm.
7. Các ràng buộc gốc của bài toán. Trị giá 19 điểm.

Ví dụ

Dữ liệu vào 1

2
2 1

Dữ liệu ra 1

6

Dữ liệu vào 2

4
3 4 2 1

Dữ liệu ra 2

232

Ghi chú

Hãy xem xét ví dụ thứ hai với thứ tự $q = [4, 3, 2, 1]$. Ban đầu, tất cả các ngôi nhà đều được kết nối với lưới điện.

1. Trong ngày đầu tiên, ngôi nhà thứ 4 bị ngắt khỏi lưới điện. Cư dân của các ngôi nhà 1 và 2 sẽ nhận thấy hàng xóm của họ không có điện và sẽ kéo cáp. Do đó, các ngôi nhà 1, 2, 4 sẽ tạo thành một nhóm kết nối bằng cáp do người dân tự kéo. Đồng thời, ngôi nhà thứ 3 sẽ được coi là một nhóm riêng biệt. Số lượng nhóm là 2.
2. Trong ngày thứ hai, ngôi nhà thứ 3 bị ngắt khỏi lưới điện. Cư dân của các ngôi nhà 1 và 2 sẽ lại kéo cáp. Tất cả 4 ngôi nhà sẽ được kết nối bằng cáp. Số lượng nhóm là 1.
3. Vào ngày thứ ba, ngôi nhà thứ 2 bị ngắt điện. Kết quả là, cả hai sợi cáp trước đó gắn vào ngôi nhà thứ 2 đều bị loại bỏ. Bây giờ có hai nhóm — $[1, 3, 4]$ và $[2]$. Số lượng nhóm là 2.
4. Cuối cùng, ngôi nhà thứ nhất bị ngắt điện. Cả hai sợi cáp trước đó gắn vào ngôi nhà thứ nhất đều bị loại bỏ và mỗi ngôi nhà sẽ tạo thành một nhóm riêng biệt. Số lượng nhóm là 4.

Kết quả là, độ bất ổn của thứ tự $q = [4, 3, 2, 1]$ là $2+1+2+4=9$.