Однажды мальчик Вася оказался в лабиринте, состоящем из (n + 1) комнат, пронумерованных от 1 до (n + 1). Первоначально Вася находится в первой комнате, а чтобы выйти из лабиринта, нужно попасть в (n + 1)-ю.
Лабиринт устроен следующим образом. В каждой комнате лабиринта есть два односторонних портала. Рассмотрим комнату с номером i (1 ≤ i ≤ n), с помощью первого портала можно перейти из нее в комнату с номером (i + 1), с помощью второго можно перейти из нее в комнату с номером pi, где 1 ≤ pi ≤ i.
Чтобы не заблудиться Вася решил действовать следующим образом.
- Каждый раз когда Вася приходит в какую-то комнату он рисует на ее потолке крестик. Изначально, Вася рисует крестик на потолке комнаты 1.
- Пусть Вася находится в комнате i и уже нарисовал крестик на ее потолке. Тогда, если сейчас на потолке нарисовано нечетное количество крестиков, Вася будет пользоваться вторым порталом (он ведет в комнату pi), иначе Вася будет пользоваться первым порталом.
Помогите Васе определить, сколько раз ему придется воспользоваться порталами, чтобы попасть в комнату (n + 1) в конечном итоге.
Выходные данные
Выведите одно число — количество перемещений, за которое мальчик выберется из лабиринта. Поскольку это число может быть достаточно большим, выведите его по модулю 1000000007 (109 + 7).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
4
|
|
2
|
4
1 1 2 3
|
20
|
|
3
|
5
1 1 1 1 1
|
62
|