B. Длинный путь
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Однажды мальчик Вася оказался в лабиринте, состоящем из (n + 1) комнат, пронумерованных от 1 до (n + 1). Первоначально Вася находится в первой комнате, а чтобы выйти из лабиринта, нужно попасть в (n + 1)-ю.

Лабиринт устроен следующим образом. В каждой комнате лабиринта есть два односторонних портала. Рассмотрим комнату с номером i (1 ≤ i ≤ n), с помощью первого портала можно перейти из нее в комнату с номером (i + 1), с помощью второго можно перейти из нее в комнату с номером pi, где 1 ≤ pi ≤ i.

Чтобы не заблудиться Вася решил действовать следующим образом.

  • Каждый раз когда Вася приходит в какую-то комнату он рисует на ее потолке крестик. Изначально, Вася рисует крестик на потолке комнаты 1.
  • Пусть Вася находится в комнате i и уже нарисовал крестик на ее потолке. Тогда, если сейчас на потолке нарисовано нечетное количество крестиков, Вася будет пользоваться вторым порталом (он ведет в комнату pi), иначе Вася будет пользоваться первым порталом.

Помогите Васе определить, сколько раз ему придется воспользоваться порталами, чтобы попасть в комнату (n + 1) в конечном итоге.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 103) — число комнат. Во второй строке записаны n целых чисел pi (1 ≤ pi ≤ i) — номера комнат, в которые можно попасть из i-й комнаты, если пользоваться вторым порталом.

Выходные данные

Выведите одно число — количество перемещений, за которое мальчик выберется из лабиринта. Поскольку это число может быть достаточно большим, выведите его по модулю 1000000007 (109 + 7).

Примеры
Входные данные
2
1 2
Выходные данные
4
Входные данные
4
1 1 2 3
Выходные данные
20
Входные данные
5
1 1 1 1 1
Выходные данные
62