Самое трудное в работе жюри кроме придумывания задач, написания корректных решений, создания чекеров, валидаторов, тестов, условий и разборов — это расставление задач между собой в уже готовом комплекте. Никто не знает, как это правильно делать, поэтому для этого используется древняя техника.

Это тайное знание состоит в одном простом алгоритме:

1. Вначале каждая задача из комплекта сортируется по сложности, самой сложной из них присваивается 1, второй по сложности — 2, и так далее.
2. Затем берётся шаблон — какая-то перестановка чисел от 1 до N, где N — количество задач в контесте, которая отвечает за расстановку задач по сложности.
3. После этого ищется левый подшаблон и правый подшаблон. Для этого в шаблоне находится позиция самой сложной задачи. Тогда левый подшаблон — это шаблон, отвечающий за все те задачи, которые находятся до самой сложной (если самая трудная задача была первой в шаблоне, то он становится пустым), а правый подшаблон — это шаблон, отвечающий за все те задачи, которые находятся после самой сложной (если самая трудная задача была последней в шаблоне, то он становится также пустым).
4. Два шаблона называются эквивалентными, если они оба пустые, либо позиция самой трудной задачи у них совпадает, их левые подшаблоны эквивалентны, и их правые подшаблоны также эквивалентны.
5. И финальный шаг для расставления задач в контесте — это выбрать произвольный эквивалентный шаблон к данному вначале.

Проблема в этом одна. Жюри всегда брали один и тот же древний шаблон, и настало время его поменять, но для этого нужно посчитать количество эквивалентных ему шаблонов. Жюри сейчас занято перестановкой задач в другом контесте и ответами на вопросы участников, поэтому эта задача достаётся Вам.

В первой строке вводится одно целое число N — количество задач в комплекте (1 ≤ N ≤ 10⁵).

Во второй строке вводятся N целых чисел p_i через пробел — описание проверяемого Вами шаблона (1 ≤ p_i ≤ N, все p_i различные).

Выведите количество шаблонов, эквивалентных данному, по модулю 10⁹+7. То есть, найдите остаток при делении количества шаблонов на 1 000 000 007.

В первом примере существуют только два эквивалентных шаблону из ввода шаблона — (2,1,3) и (3,1,2).