407B.md (1894B)
1 Source: https://codeforces.com/problemset/problem/407/B 2 3 B. Long Path 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 One day, little Vasya found himself in a maze consisting of (*n* + 1) rooms, numbered from 1 to (*n* + 1). Initially, Vasya is at the first room and to get out of the maze, he needs to get to the (*n* + 1)-th one. 22 23 The maze is organized as follows. Each room of the maze has two one-way portals. Let's consider room number *i* (1 ≤ *i* ≤ *n*), someone can use the first portal to move from it to room number (*i* + 1), also someone can use the second portal to move from it to room number *p**i*, where 1 ≤ *p**i* ≤ *i*. 24 25 In order not to get lost, Vasya decided to act as follows. 26 27 * Each time Vasya enters some room, he paints a cross on its ceiling. Initially, Vasya paints a cross at the ceiling of room 1. 28 * Let's assume that Vasya is in room *i* and has already painted a cross on its ceiling. Then, if the ceiling now contains an odd number of crosses, Vasya uses the second portal (it leads to room *p**i*), otherwise Vasya uses the first portal. 29 30 Help Vasya determine the number of times he needs to use portals to get to room (*n* + 1) in the end. 31 32 Input 33 34 The first line contains integer *n* (1 ≤ *n* ≤ 103) — the number of rooms. The second line contains *n* integers *p**i* (1 ≤ *p**i* ≤ *i*). Each *p**i* denotes the number of the room, that someone can reach, if he will use the second portal in the *i*-th room. 35 36 Output 37 38 Print a single number — the number of portal moves the boy needs to go out of the maze. As the number can be rather large, print it modulo 1000000007 (109 + 7). 39 40 Examples 41 42 Input 43 44 ``` 45 2 46 1 2 47 ``` 48 49 Output 50 51 ``` 52 4 53 ``` 54 55 Input 56 57 ``` 58 4 59 1 1 2 3 60 ``` 61 62 Output 63 64 ``` 65 20 66 ``` 67 68 Input 69 70 ``` 71 5 72 1 1 1 1 1 73 ``` 74 75 Output 76 77 ``` 78 62 79 ```