**Note: An equivalent version of this problem is also available on DMOJ here**

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:

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

#### Constraints

for all

It may help to know that .

#### Sample Input

```
4
1 2 2 3
```

#### Sample Output

`8 23 28 12`

#### Explanation for Sample Input

, .

There are 4 distinct *1-products*:

There are 6 distinct *2-products*.

Their sum is .

There are 4 distinct *3-products*.

Their sum is .

The only *4-product* is .

## Comments