## Back To School '18: An FFT Problem

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

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:

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

It may or may not help to know that .

#### 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