BTtown 由 $n$ 間房屋組成，編號為 $1$ 到 $n$。房屋位置由排列 $p_1, \dots, p_n$ 描述：房屋 $i$ 與 $p_i$ 被視為鄰居。若 $p_i = i$，則表示第 $i$ 間房屋沒有鄰居。
由於城市中央發電廠的技術問題，市政府被迫逐一切斷房屋的電力供應。假設切斷順序由排列 $q_1, \dots, q_n$ 描述。最初，每間房屋都連接到電網。在第 $i$ 天，編號為 $q_i$ 的房屋會被切斷與電網的連接。
為了緩解這種情況，市民必須幫助有需要的鄰居：仍然連接到電網的房屋居民，需要鋪設電纜連接到已被切斷電網的鄰居房屋。值得注意的是，這並不會使鄰居房屋重新連接回電網。
在任何時間點，以下規則成立： 當且僅當兩間房屋互為鄰居，且其中一間連接到電網、另一間未連接到電網時，兩者之間會有一條電纜。 因此，如果兩間房屋都已從電網切斷，則原本可能存在於兩者之間的電纜會被移除。
在每一天結束時，城市會被劃分為由市民鋪設的電纜所連接的房屋群組。為了分析電網的穩定性，追蹤這些群組的數量非常重要。切斷順序 $q$ 的「不穩定度」（instability）定義為 $n$ 天中每天群組數量的總和。
市政府尚未決定切斷順序 $q$，現在需要計算所有可能順序下的不穩定度總和。請協助城市計算該數值對 $10^9 + 7$ 取模後的結果。
輸入格式
第一行包含一個整數 $n$ ($1 \le n \le 10^6$)。 第二行包含 $n$ 個以空格分隔的整數 $p_1, \dots, p_n$ ($1 \le p_i \le n, p_i \neq p_j$ 若 $i \neq j$)。
輸出格式
輸出一個整數，代表所有可能切斷順序的不穩定度總和除以 $10^9 + 7$ 的餘數。
子任務
本題包含 7 個子任務，滿足以下要求：
- $n \le 8$。配分 8 分。
- $n \le 18$。配分 10 分。
- $n \le 30$。配分 13 分。
- $n \le 2000$。配分 22 分。
- $n \le 100000, p_i = n - i + 1$。配分 16 分。
- $n \le 100000$。配分 12 分。
- 原始問題限制。配分 19 分。
範例
範例 1
輸入
2 2 1
輸出
6
範例 2
輸入
4 3 4 2 1
輸出
232
說明
讓我們考慮第二個範例，切斷順序為 $q = [4, 3, 2, 1]$。最初，所有房屋都連接到電網。
- 第一天，第 4 間房屋被切斷。房屋 1 和 2 的居民會發現他們的鄰居沒有電力，因此會鋪設電纜。因此，房屋 1、2、4 形成一個由市民鋪設電纜連接的群組。同時，第 3 間房屋被視為一個獨立的群組。群組數量為 2。
- 第二天，第 3 間房屋被切斷。房屋 1 和 2 的居民會再次鋪設電纜。所有 4 間房屋都將透過電纜連接。群組數量為 1。
- 第三天，第 2 間房屋被切斷。結果，先前連接到第 2 間房屋的兩條電纜都被移除。現在有兩個群組 — $[1, 3, 4]$ 和 $[2]$。群組數量為 2。
- 最後，第 1 間房屋被切斷。連接到第 1 間房屋的兩條電纜都被移除，每間房屋都形成一個獨立的群組。群組數量為 4。
因此，順序 $q = [4, 3, 2, 1]$ 的不穩定度為 $2+1+2+4=9$。