D. Урт зам

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэг өдөр, Бяцхан Вася өөрийгөө $1$-ээс $(n + 1)$ хүртэл дугаарлагдсан $(n + 1)$ өрөөнөөс тогтох төөрдөг байшинд байгааг мэджээ. Анхандаа, Вася эхний өрөөнд байх ба төөрдөг байшингаас гарахын тулд тэрээр $(n + 1)$-дэх өрөөнд очих хэрэгтэй юм.

Төөрдөг байшин нь дараах байдлаар зохион байгуулагдсан байна. Төөрдөг байшингийн өрөө болгонд 2 ширхэг нэг-талын шилжигч хаалга байдаг. $i$ $(1 ≤ i ≤ n)$ дугаартай өрөөг авч үзье, хэн нэгэн эхний шилжигч хаалгыг хэрэглэн уг өрөөнөөс $(i + 1)$ дугаартай өрөө уруу шилжиж болно, мөн хэн нэгэн 2-дахь шилжигч хаалгыг хэрэглэн уг өрөөнөөс $p_{i}$ дугаартай өрөө уруу шилжиж болно, энд $1 ≤ p_{i} ≤ i$ байна.

Төөрөхгүй нь тулд, Вася дараах байдлаар хөдлөхөөр шийджээ.

  • Вася ямар нэг өрөөнд орж ирэх болгондоо, тэрээр тус өрөөний таазан дээр хэрээс будаж үлдээнэ. Анхандаа, Вася $1$-дэх өрөөний таазан дээр хэрээс будаж үлдээх юм.
  • Вася $i$-дахь өрөөнд байгаа ба аль хэдийн тус өрөөний таазан дээр хэрээс будаж үлдээсэн гэж үзье. Тэгвэл, хэрэв тааз нь одоо сондгой тооны хэрээс агуулж байвал, Вася 2-дахь шилжигч хаалгыг (энэ нь $p_{i}$-дахь өрөөнд хүргэнэ) хэрэглэнэ, бусад тохиолдолд эхний шилжигч хаалгыг хэрэглэнэ.

Вася-д эцэст нь $(n + 1)$-дэх өрөөнд очихын тулд шилжигч хаалгыг хэрэглэх тоог тодорхойлж өгнө үү.

Оролт

Эхний мөрөнд өрөөний тоог илэрхийлэх бүхэл тоо $n$ ($1 ≤ n ≤ 10^{3}$) өгөгдөнө. 2-дахь мөрөнд $n$ ширхэг бүхэл тоо $p_{i}$ ($1 ≤ p_{i} ≤ i$)-ууд өгөгдөнө. $p_{i}$ бүр нь хэрэв хэн нэгэн $i$-дахь өрөөнд 2-дахь шилжигч хаалгыг хэрэглэвэл шилжин очих өрөөний дугаарыг илэрхийлнэ.

Гаралт

Хүү төөрдөг байшингаас гарахын тулд хэрэглэх шилжих хөдөлгөөний тоог илэрхийлэх ганц тоог хэвлэнэ. Тоо нь маш том байж болох учраас, уг тоог $1000000007$ $(10^{9} + 7)$ модулаар бодож хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
2
1 2
Гаралт
4
Оролт
4
1 1 2 3
Гаралт
20
Оролт
5
1 1 1 1 1
Гаралт
62
Сэтгэгдлүүдийг ачааллаж байна...