В городе 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$ называется сумма количеств таких групп за каждый из $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. Наконец, отключается первый дом. Оба кабеля, ранее присоединенные к первому дому, удаляются, и каждый дом образует отдельную группу. Количество групп равно 4.

В результате нестабильность порядка $q = [4, 3, 2, 1]$ равна $2+1+2+4=9$.