Little P is taking a political science exam consisting of $n$ true/false questions. For some questions, Little P can guess an answer based on his own knowledge; however, for questions he has no idea about, he obtains the standard answer through some means and fills it in. Little P has the ability to turn back time, so he can take the same exam $q$ times, although his strategy may differ each time. As everyone knows, only an AK (getting all questions correct) can satisfy Little P's desires. Since the answer to each question is unknown, Little P wants to know how many possible standard answer keys exist such that he can achieve an AK in at least one of the exams.
Input
The first line contains two integers $n$ and $q$.
The following $q$ lines each contain a string of length $n$ consisting of the characters 0, 1, and ?. A digit means the answer is guessed by Little P (it matches that specific character), and ? means he obtained the standard answer for that question (it matches any character).
Output
Output a single integer representing the number of $0/1$ strings $s$ of length $n$ such that $s$ matches at least one of the $q$ given strings.
Examples
Input 1
4 2 ??01 1??1
Output 1
6
Note 1
The valid strings are: 0001, 0101, 1001, 1101, 1011, 1111
Constraints
| Subtask | $n\leq$ | $q\leq$ | Special Properties | Score |
|---|---|---|---|---|
| 1 | $20$ | $20$ | $3$ | |
| 2 | $30$ | $20$ | $12$ | |
| 3 | $25$ | $30$ | $11$ | |
| 4 | $30$ | $30$ | $6$ | |
| 5 | $30$ | $100$ | Total number of question marks $\leq 40$ | $11$ |
| 6 | $30$ | $50$ | $16$ | |
| 7 | $30$ | $100$ | $41$ |