Mr. C has had a change of heart from being a lonely developer to finally getting a girlfriend, Ms. C (they are not related by blood). As the courteous fellow he is, he has decided to buy some flowers for her.

Ms. C wants flowers with flower costing , a positive integer. The store, Carol's Flowers, has flowers, where . Each flower can only be bought once, and since Mr. C lives in a computer science problem, the cost of the flowers are exponential. In other words, the second flower he buys is the price of the flower squared, and the third flower he buys is the price of the flower cubed, and so on.

Mr. C is poor, but he needs to satisfy Ms. C. Can you find out the minimum value Mr. C has to pay for flowers?

#### Input Specification

The first line of input contains integers, and .

The next lines contain integer each. The line contains the positive integer .

- For 5 of the 15 available marks, and .
- For an additional 5 of the 15 available marks, and .

#### Output Specification

A single integer representing the minimum price Mr. C has to pay for flowers mod .

#### Sample Input

```
7 3
2
5
2
9
100
56
3
```

#### Sample Output

`15`

#### Explanation for Sample Output

The cheapest way to buy flowers is to buy the last flower, the third flower, and the first flower. That is, is the minimum price.

## Comments

Where would we input i?

sad to find that nobody replied to your comment in 1 whole year.