The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. New Year Garland

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAs Gerald, Alexander, Sergey and Gennady are already busy with the usual New Year chores, Edward hastily decorates the New Year Tree. And any decent New Year Tree must be decorated with a good garland. Edward has lamps of *m* colors and he wants to make a garland from them. That garland should represent a sequence whose length equals *L*. Edward's tree is *n* layers high and Edward plans to hang the garland so as to decorate the first layer with the first *l*_{1} lamps, the second layer — with the next *l*_{2} lamps and so on. The last *n*-th layer should be decorated with the last *l*_{n} lamps,

Edward adores all sorts of math puzzles, so he suddenly wondered: how many different ways to assemble the garland are there given that the both following two conditions are met:

- Any two lamps that follow consecutively in the same layer should have different colors.
- The sets of used colors in every two neighbouring layers must be different. We consider unordered sets (not multisets), where every color occurs no more than once. So the number of lamps of particular color does not matter.

Help Edward find the answer to this nagging problem or else he won't manage to decorate the Tree by New Year. You may consider that Edward has an unlimited number of lamps of each of *m* colors and it is not obligatory to use all *m* colors. The garlands are considered different if they differ in at least one position when represented as sequences. Calculate the answer modulo *p*.

Input

The first line contains three integers *n*, *m* and *p* (1 ≤ *n*, *m* ≤ 10^{6}, 2 ≤ *p* ≤ 10^{9}) which are the number of the tree's layers, the number of the lamps' colors and module correspondingly. The next line contains *n* integers *l*_{i} (1 ≤ *l*_{i} ≤ 5000, ).

Output

Print the only integer — the number of garlands modulo *p*.

Examples

Input

3 2 1000

3 1 2

Output

8

Input

2 3 1000

2 2

Output

24

Input

1 1 1000

5

Output

0

Note

In the first sample the following variants are possible: 121|1|12, 121|1|21, 121|2|12, 121|2|21, 212|1|12, 212|1|21, 212|2|12, 212|2|21. In the second sample the following variants are possible: 12|13, 12|23, 12|31, 12|32 and so on.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2022 08:18:15 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|