Because of her vendetta against alcohol, Diona seeks to mix possibly the most disgusting alcoholic drinks and ruin the Mondstadt wine industry.

Today, Diona still tries to mix disgusting alcoholic drinks. There are n customers in Bartender of the Cat's Tail, and Diona has mixed n different cups of drinks. The i-th customer will like only the i-th cup of drinks and don't like other n-1 cups of drinks. Diona deliberately make all drinks the same appearance and randomly place them, because she thinks most customers will get drinks they won't like then.

Actually, after all customers get drinks, each of them will taste and recognize the type of his drink, and then they will exchange their drinks to make sure each of them can get his favorite drink. Exchanging can be tiring, but these customers are clever, they always exchange optimally to minimize the number of exchanging. (For example, if 5 customers get the 2-nd, 4-th, 5-th, 1-st, 3-rd cup of drink respecively, then customer 1 will exchange with customer 4, customer 3 will exchange with customer 5, customer 2 will exchange with customer 4, so each customer gets his favorite drink within 3 exchanges. It can be shown that 3 is the minimum number of exchanges.)

As a result, today, Diona still fails to mix disgusting alcoholic drinks. But gradually Diona gets interested in the optimal way for customers to exchange, she want to calculate the expected value of the minimum number of exchanging in different cases. Specifically, Diona wonder the expected value before no customer get any drink and when everytime a customer get a drink.

It can be shown that the expected value can be represented as a rational number . As P and Q can be very large, you should output . Recall that , and is defined as a number which can satisfy .

输入描述:

The first line contains a single integer n () --- the number of customers in Bartender of the Cat's Tail today.

The second line contains n integers  (), which means the i-th customer get the -th cup of drink, and you need to calculate the expected value of the minimum number of exchanging.

It is guaranteed that all of  are distinct, i.e. no two or more customers will get the same cup of drink.

输出描述:

Output n+1 integers. The first integer is the expected value of the minimum number of exchanging before no customer get any drink, and the i-th integers in following n integers is the expected value of the minimum number of exchanging after i customers get their drinks.

1
1

0
0

3
2 3 1

166374060
499122178
2
2

备注:

In the second example, the output consist of 4 integers, which is explained as following.

Before no customer get any drink: There are 6 possible situations --- three customers get the [1-st, 2-nd, 3-rd] or [1-st, 3-rd, 2-nd] or [2-nd, 1-st, 3-rd] or [2-nd, 3-rd, 1-st] or [3-rd, 1-st, 2-nd] or [3-rd, 2-nd, 1-st] cup of drink respectively. It costs 0, 1, 1, 2, 2, 1 exchanges in these situations respectively, so the expected value of the number of exchange is , which is 166374060 after modulo.

After costumer 1 gets the 2-nd cup of drink: There are 2 possible situations --- three customers get the [2-nd, 1-st, 3-rd] or [2-nd, 3-rd, 1-st] cup of drink respectively. It costs 1, 2 exchanges in these situations respectively, so the expected value of the number of exchange is , which is 499122178 after modulo.

After costumer 2 gets the 3-rd cup of drink: There is only one possible situation --- three customers get the [2-nd, 3-rd, 1-st] cup of drink respectively. It costs 2 exchanges in this situation, so the expected value of the number of exchange is 2, which is still 2 after modulo.

After costomer 3 gets the 1-st cup of drink: The last customer just chooses his only choice. There is still only one possible situation and the expected value is still 2.