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 个子任务，满足以下要求：

1. $n \le 8$。分值 8 分。
2. $n \le 18$。分值 10 分。
3. $n \le 30$。分值 13 分。
4. $n \le 2000$。分值 22 分。
5. $n \le 100000, p_i = n - i + 1$。分值 16 分。
6. $n \le 100000$。分值 12 分。
7. 原始问题约束。分值 19 分。

样例

样例输入 1

2
2 1

样例输出 1

6

样例输入 2

4
3 4 2 1

样例输出 2

232

说明

考虑第二个样例，切断顺序为 $q = [4, 3, 2, 1]$。最初，所有房屋都连接到电网。

1. 第一天，第 4 座房屋被切断。房屋 1 和 2 的居民会注意到他们的邻居没有电，并铺设电缆。因此，房屋 1、2、4 形成一个由市民铺设电缆连接的组。同时，第 3 座房屋被视为一个独立的组。组的数量为 2。
2. 第二天，第 3 座房屋被切断。房屋 1 和 2 的居民将再次铺设电缆。所有 4 座房屋都将通过电缆连接。组的数量为 1。
3. 第三天，第 2 座房屋被断开。结果，之前连接到第 2 座房屋的两条电缆都被移除。现在有两个组 —— $[1, 3, 4]$ 和 $[2]$。组的数量为 2。
4. 最后，第 1 座房屋被断开。连接到第 1 座房屋的两条电缆都被移除，每座房屋都形成一个独立的组。组的数量为 4。

因此，切断顺序 $q = [4, 3, 2, 1]$ 的不稳定性为 $2+1+2+4=9$。