PROBLEM STATEMENT

Bob's little sister Alice is nine years old.
Bob is testing her mathematical prowess by asking her to compute the remainder a number gives when 
divided by 9.



Today, Bob gave Alice exactly N such questions.
We will number the questions 0 through N-1.
In each question, Bob gave Alice the same M-digit number.
(Note that Bob's number is allowed to have some leading zeros.)



In some of those cases Alice may have skipped some of the digits when reading the number.
However, she never made any other mistakes in her calculations.
For example, if Bob gave Alice the number 012345 three times, she may have read it as 0145 the 
first time, 012345 the second time, and 135 the third time.
Then, her answers would be 145 modulo 9 = 1, 12345 modulo 9 = 6, and 135 modulo 9 = 0.



You are given the int N and a vector <int> d with M elements.
For each i, the number d[i] corresponds to the digit of the order 10^i in Bob's number.
For each i and j, Alice read digit i when answering question j if and only if bit number j of the 
number d[i] is 1.



For example, suppose that d[3] = 6.
In binary, 6 is 110.
In other words, the binary digits number 0, 1, and 2 are 0, 1, and 1.
Hence, Alice skipped the corresponding digit in question 0 but she read it in questions 1 and 2.



A surprising thing happened in today's experiment:
For each of the N questions, Alice's answer was that the remainder is 0.
Bob found that interesting.
He now wonders: given N and d, how many different M-digit numbers have this property?



Let X be the answer to Bob's question.
Compute and return the value (X modulo 1,000,000,007).


DEFINITION
Class:Nine
Method:count
Parameters:int, vector <int>
Returns:int
Method signature:int count(int N, vector <int> d)


CONSTRAINTS
-N will be between 1 and 5, inclusive.
-The number of elements in d will be between 1 and 5,000, inclusive.
-All elements in d must be between 0 and 2N-1, inclusive
-d will be such that in each question Alice will read at least one digit.


EXAMPLES

0)
2
{1,2}

Returns: 4

In this case we have N=2 questions and Bob's number has two digits.
When processing question 0, Alice only reads digit 0 (the last digit of the number).
As her answer is that the remainder is 0, this digit must be either 0 or 9.
When processing question 1, Alice only reads digit 1 (the first digit of the number).
As her answer is that the remainder is 0 again, this digit must also be either 0 or 9.
Thus there are four possible numbers: 00, 09, 90, and 99.

1)
2
{1,2,3}

Returns: 16



2)
1
{0,0,1}

Returns: 200



3)
5
{1,3,5,8,24,22,25,21,30,2,4,0,6,7,9,11,14,13,12,15,18,17,16,19,26,29,31,28,27,10,20,23}

Returns: 450877328



4)
5
{31,31,31,31,31}

Returns: 11112



 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.