WPC5F - Parade

It is the Annual Parade of the Galactical Wars. Great men and women from around the cosmos have come to view this spectacular event. To make this a special occasion, the leaders in galaxy H2 have decided to arrange his participants in a particularly beautiful order.

Firstly, they have chosen n particularly suited participants. These n participants have distinct heights ranging from 1 to n. They have arranged them in some way, so that the height of the ith student is H(i).

The sworn enemies of H2, galaxy H3 have obtained some secret information on this arrangement. They know that there is a set of elements A (containing total k indices), such that H(j) < H(j-1) IF AND ONLY IF j belongs to A. As a Martian on H3, your organizer asks you to find the number of such possible configurations that H2 could have made.

Input

A single line containing space separated integers: n and k.

Next line containing k indices as explained in the problem.

Output

A single line containing the number of ways to arrange participants modulo 1000000009 (10 ^ 9 + 9)

h3>Constraints

1 <= n <= 700

0 <= k <= n-1

2 <= i <= n (i is an index)

All i’s are unique.

Examples

Input:
3 1
2

Output:
2

Explanation

There are 2 possible ways to arrange the participants, where their heights are: 2 1 3 or 3 1 2

Note 3 2 1 is not a valid ordering since h(3) < h(2).


Added by:triveni
Date:2014-03-29
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACA judge IITK, WPC5

hide comments
2016-02-13 03:00:18 Min_25
There is something wrong with the I/O files.

Assertion failed with
1. assert(0 <= K && K <= N - 1); // it seems that K can be >= N.
2. assert(2 <= i && i <= N); // Perhaps i can be 1.

Last edit: 2016-02-13 17:07:33
2015-06-03 00:18:49 (Tjandra Satria Gunawan)(曾毅昆)
My Accepted algo on PERMUT3 problem getting WA here, thats weird! :-/

EDIT: Finally AC, I forgot to sort i ;-)

Last edit: 2015-06-03 00:34:14
2014-04-01 16:38:11 Jacob Plachta
The constraints say "m" instead of "k".

Ans-> thanks for pointing it out. Corrected.

Last edit: 2014-04-01 16:38:48
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.