## An FFT Problem V

View as PDF

Points: 35
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

I have a 1-indexed array named with elements.

I define a k-product as taking a subset of size from the set and taking the product of the values of at those indexes.

For example, if , one valid 3-product is .

I define a k-sum of an array as the sum of all distinct k-products that can be formed with it. Two k-products are considered distinct if the subset of indexes are different, regardless of the values at the indexes.

For all , find the k-sum of , each modulo .

#### Input Specification

The first line of input will contain a single integer .

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

#### Output Specification

On one line, print space-separated integers, the integer representing the -sum of , 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 .

#### Constraints

for all

It may help to know that .

Please note that this problem does not have partials enabled.

4
1 2 2 3

8 23 28 12

#### Explanation for Sample Input

, .

There are 4 distinct 1-products:

Their sum is 8.

There are 6 distinct 2-products.

Their sum is .

There are 4 distinct 3-products.

Their sum is .

The is one 4-product

.

The sum is .