유전병

정민은 단세포생물이다. JMPABU(JeongMin is Paramecium & Amoeba Based Unicellular organism)라는 이름이 말해 주듯이 짚신벌레와 아메바를 닮았다. 정민을 1년 남짓 관찰해서 다음 두 가지 특징을 알아냈다.

• $D$세대 정민이 자식을 낳으면 그 자식은 $D+1$세대가 된다. $D$세대 정민은 살면서 정확히 $D+1$마리의 자식을 남기고 죽는다.
• 정민에게는 특이한 유전자가 있다. 이 유전자는 태어난 순서에 따라 유전병을 일으키는 유전자가 되기도 한다.

내가 가진 정민은 0세대 한 마리뿐이고, 이 정민에게 0번을 붙였다. 자손에게도 편의를 위해 번호를 붙인다. 자식에게 아직 번호를 붙이지 않은 정민 중에서 번호가 가장 작은 정민을 고른 다음, 그 자식들에게 태어난 순서대로 아직 쓰지 않은 가장 작은 번호부터 차례로 붙인다. 이 과정을 반복하면 아래 그림처럼 번호가 붙는다.

어떤 순서로 태어난 정민이 유전병에 걸리는지 알아보려고 실험을 이어 가고 있다. 방법은 간단하다. 태어난 순서를 하나씩 따라가면서 그 자리에 있는 정민을 검사한다. 예를 들어 0세대 정민이 1번째로 낳은 자식, 그 자식이 2번째로 낳은 자식, 다시 그 자식이 1번째로 낳은 자식을 차례로 보는 식이다. 이렇게 따라가면 보게 되는 정민의 번호는 순서대로 1, 3, 7이다. 그런데 세대가 커질수록 번호가 너무 커져서 손으로 따라가기 어렵다. 도움이 필요하다.

첫째 줄에 조사하려는 정민의 세대 $D$ ($1 \le D \le 100$)가 주어진다.

둘째 줄에 정수 $D$개가 공백으로 구분되어 주어진다. $i$번째 정수 $d_i$ ($1 \le d_i \le i$)는 $i-1$세대 정민이 $d_i$번째로 낳은 자식을 보겠다는 뜻이다.

$D$개의 줄을 출력한다. $k$번째 줄에는 주어진 입력을 따라가면서 보게 되는 $k$세대 정민의 번호를 출력한다. 번호가 매우 커질 수 있으므로 번호를 1,000,000,007로 나눈 나머지를 출력한다.