## COCI '15 Contest 5 #3 Perica

View as PDF

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem types

"I'm stopping by Žnidaršić's house, you play the piano, Perica."

And so, Perica began playing the piano. His piano consists of keys. Each key has a value written on it, . When Perica plays the piano, he presses exactly different keys at the same time. The piano is a bit strange because, after pressing keys at the same time, it will play only the key with the largest value. Perica is going to play each combination of keys on the piano and he wants to know the sum of values of the keys that will be played.

Help Perica determine the remainder of that number modulo .

#### Input

The first line of input contains two integers and . The following line of input contains integers .

#### Output

The first and only line of output must contain the required number from the task.

#### Scoring

In test cases worth 40% of total points, it will additionally hold .

#### Sample Input 1

5 3
2 4 2 3 4

#### Sample Output 1

39

#### Explanation for Sample Output 1

All selections of keys are: [2, 4, 2], [2, 4, 3], [2, 4, 4], [2, 2, 3], [2, 2, 4], [2, 3, 4], [4, 2, 3], [4, 2, 4], [4, 3, 4], [2, 3, 4].

#### Sample Input 2

5 1
1 0 1 1 1

#### Sample Output 2

4

#### Sample Input 3

5 2
3 3 4 0 0

#### Sample Output 3

31