To prepare for the upcoming school year, Richard has bought books for his English class. Each book is assigned a value, , Richard's willingness to read that book.

Richard wants to choose of the books and calculate his willingness to read those books. The willingness to read those books is the product of the willingness to read each individual book. For example, if he bought books of value , and he chose books with indices , the willingness to read those books would be .

Richard wants the *sum* of the willingness of all **distinct combinations** of books for all values of .

However, since Richard does not like large numbers, he wants each *sum* modulo .

Two combinations are considered **distinct** if the indices of the books chosen are different, **regardless of the values of the books**.

#### Input Specification

The first line of input will contain a single integer , the number of books that Richard bought.

The second line of input will contain space-separated integers, the integer representing , the value of each book.

#### Output Specification

On one line, print space-separated integers, the integer representing the *sum* of the willingness of all **distinct combinations** of choosing books, modulo .

We define modulo in the 2 equivalent ways:

- Taking the remainder of , adding if the result is negative.
- Subtracting from , or adding to , until is in the interval .

It may or may not help to know that .

#### Constraints

##### Subtask 1 [5%]

##### Subtask 2 [10%]

##### Subtask 3 [35%]

##### Subtask 4 [50%]

No additional constraints.

#### Sample Input 1

```
4
1 2 2 3
```

#### Sample Output 1

`8 23 28 12`

#### Explanation for Sample Output 1

, .

There are distinct combinations to read book:

Their sum is .

There are distinct combinations to read books.

Their sum is .

There are distinct combinations of reading books.

Their sum is .

The only distinct combination of reading books is .

#### Sample Input 2

```
3
-1 -1 -1
```

#### Sample Output 2

`998244350 3 998244352`

## Comments