Chef has a sequence of integers A1,A2,...,AN

A1,A2,...,AN. He takes a sheet of paper and for each non-empty subsequence B

B of this sequence, he does the following:

1. For each integer which appears in B
2. B, count its number of occurrences in the sequence B
3. B.
4. Choose the integer with the largest number of occurrences. If there are several options, choose the smallest one.
5. Finally, write down the chosen integer (an element of B
6. B) on the sheet of paper.

For each integer between 1

1 and N

N inclusive, find out how many times it appears on Chef's sheet of paper. Since these numbers may be very large, compute them modulo 1,000,000,007

1,000,000,007 (10

9

+7

109+7).