Inherited disease Batch Compilation commands

정민이라는 생물을 아는가? 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$개의 정수가 주어지는데, 차례대로 $d_{i}$ $(1 \le i \le D, 1 \le d_{i} \le i)$가 공백으로 구분되어 주어지며, $d_{i}$는 $i-1$ 세대의 정민이 $d_{i}$번째로 낳은 자식을 보겠다는 의미이다.

출력 형식

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

입력

3
1 2 1

출력

1
3
7