supersuma

We are given an array $A$ of length $N$. The green operation applied to $A$ consists of two steps:

• We create an array $B$, which is at first empty. We consider all subsets of $A$, including the empty subset, we compute the sum of the values there and then we add these sums in $B$.
• $A$ becomes $B$ and $B$ is once again empty.

Task

You must print the sum modulo $M$ of the values from $A$ after applying the green operation $K$ times.

Input data

The input will contain on the first line $N$, $K$ and $M$. The next line will contain the values from array $A$.

Output data

The first line will contain a single number, the required sum.

Constraints and clarifications

• $1 \leq N \leq 50$
• $1 \leq K \leq 10^9$
• $1 \leq M \leq 10^9 + 7$
• $0 \leq A_i \leq M$
• $M$ is odd.

Example 1

stdin

3 1 9999
1 2 3

stdout

24

Explanation

In the first example, array $A$ after the green operation is $0 \ 1 \ 2 \ 3 \ 3 \ 4 \ 5 \ 6$.

Example 2

stdin

3 4 29
0 23 0

stdout

26

Example 3

stdin

4 50000 49999
2 0 2 3

stdout

43310