Alice has n+1 items. The items have ids from 1 to n. This means there could be multiple
same ids. And it is also known that each of the items id 1 to n appears at least once in the
sequence.
Now Alice is fond of sequences. She wants to find for each integer k = 1 to n+1, the number
of subsequences of the given sequence of item ids with length k, mod 10ˆ9 + 7.
Constraints:
1 <= n <= 10^5
Input Format
The first line contains an integer n. The second line contains n+1 integers denoting the sequence of integers where each integer is between 1 and n.
Output Format
Print n+1 lines. The kth line should contain the number of different sub-sequences of the given sequence, in the same order, with length k, mod 10ˆ9 + 7.
PS: Sample test cases are different than the ones your code is evaluated on after your submission. Hence, sample #0 at the time of running your code and Testcase #0 at the time of submission will be different.
Sample input1
3
1 2 1 3
op1
3
5
4
1
sample input2
2
1 2 1
op2
2
3
1