codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```