The year is 2136. A lot of things have changed but BITS Pilani still exists. The display technology used now is a WASDLED screen.

This display technology consists of a configuration matrix containing a row of N cells each of which can display K different symbols. These K symbols are partitioned into sets X1, X2, ... , Xm

The potency of a configuration matrix is the highest integer i, 1 <= i <= m, such that there is a symbol from Xi in some cell. The configurations with odd potency are invalid whereas those with even potency are valid.

The A3 and A8 students are obsessed with this new display technology. They wonder how many different valid configurations are possible. They turn to you for a solution. Since this number can be very large output this number modulo 1000000007.

Input

A single line containing the integers N and m as described above followed by a line containing m integers: X[1], X[2], ... , X[m] denoting the size (cardinality) of each set. Output

A single line containing the number of valid configurations. Constraints

1 <= N <= 1000000000 1 <= m <= 100000 1 <= X[i] <= 1000 Sample Inputs

Input: 3 2 2 2

Output: 56 Input: 2 3 1 2 3

Output: 8

View Answers

Related Tutorials/Questions & Answers:

- Java Tutorials
- Java Code example
- Java Programming
- Java Beginners Examples
- Applet Tutorials
- Awt Tutorials
- Java Certification
- Interview Question
- Java Servlets Tutorial
- Jsp Tutorials
- Java Swing Tutorials
- JDBC Tutorial
- EJB Tutorials
- Java Server Faces (JSF) Tutorial
- WAP Tutorial
- Struts Tutorial
- JAXB Tutorial
- Spring FrameWork Tutorial
- SOA&Web Services Tutorials
- Bioinformatics Tutorials
- MySQL Tutorials
- JAVA DOM Tutorial
- XML Tutorial
- EAI Articles
- Many Programming Tutorials Links
- Tutorials Books
**Java Script Tutorial****Ajax Tutorial****Dojo Tutorials****Programming Books****Trainings****Flex****Ant****RDF**