BTtownには $1$ から $n$ までの番号が振られた $n$ 軒の家がある。家の位置は順列 $p_1, \dots, p_n$ によって記述され、家 $i$ と家 $p_i$ は隣接しているとみなされる。もし $p_i = i$ ならば、その家には隣人がいないことを意味する。
市の中心発電所における技術的な問題により、市は家を1軒ずつ送電網から切り離さなければならなくなった。切り離す順序を順列 $q_1, \dots, q_n$ とする。最初、すべての家は送電網に接続されている。$i$ 日目に、番号 $q_i$ の家が送電網から切り離される。
この状況を緩和するため、市民は困っている隣人を助ける義務がある。送電網に接続されたままの家の住人は、送電網から切り離された隣接する家へケーブルを引かなければならない。なお、これにより切り離された隣接する家が再び送電網に接続されることはない。
どの時点においても、以下が成り立つ。
- 2軒の家の間にケーブルが張られるのは、それらが隣接しており、かつそのうちの片方だけが送電網に接続されている場合のみである。
- したがって、もし両方の家が送電網から切り離された場合、それ以前にその家の間に張られていたケーブルは取り除かれる。
各日の終わりに、市は市民が引いたケーブルによって接続された家のグループに分割される。電力網の安定性を分析するために、そのようなグループの数を追跡することが重要である。切り離す順序 $q$ の「不安定さ（instability）」は、各 $n$ 日間におけるそのようなグループの数の合計である。
市はまだ順序 $q$ を決定しておらず、すべての可能な順序に対する不安定さの合計を求める必要がある。この値を $10^9 + 7$ で割った余りを計算せよ。
入力
入力の最初の行には整数 $n$ ($1 \le n \le 10^6$) が含まれる。 2行目には $n$ 個の空白区切りの整数 $p_1, \dots, p_n$ ($1 \le p_i \le n, p_i \neq p_j$ if $i \neq j$) が含まれる。
出力
すべての可能な切り離し順序に対する不安定さの合計を $10^9 + 7$ で割った余りを1つの整数として出力せよ。
小課題
この問題は以下の要件を満たす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]$ の2番目の例を考える。最初、すべての家は送電網に接続されている。
- 1日目に4番目の家が送電網から切り離される。家1と家2の住人は、隣人が電気を失ったことに気づき、ケーブルを引く。これにより、家1、2、4が市民の引いたケーブルで接続されたグループを形成する。同時に、3番目の家は独立したグループとみなされる。グループの数は2である。
- 2日目に3番目の家が送電網から切り離される。家1と家2の住人は再びケーブルを引く。4軒すべての家がケーブルで接続される。グループの数は1である。
- 3日目に2番目の家が切り離される。その結果、以前2番目の家に接続されていた両方のケーブルが取り除かれる。現在、グループは $[1, 3, 4]$ と $[2]$ の2つである。グループの数は2である。
- 最後に、1番目の家が切り離される。1番目の家に接続されていた両方のケーブルが取り除かれ、すべての家がそれぞれ独立したグループを形成する。グループの数は4である。
結果として、順序 $q = [4, 3, 2, 1]$ の不安定さは $2+1+2+4=9$ となる。