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 does not know at all, he obtains the standard answer through some means and fills it in. Little P has the ability to travel back in time, so he can take the same exam $q$ times, though his strategy may differ each time. As everyone knows, only an "AK" (getting all questions correct) can satisfy Little P's desires. Since the standard answers for each question are unknown, Little P wants to know how many possible sets of standard answers exist such that he can achieve an AK in at least one of the $q$ exams.
Input Format
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 '?'. The digits '0' and '1' represent the answers Little P guessed (which can only match the corresponding character), and '?' represents that he obtained the standard answer (which can match any character).
Output Format
Output a single integer representing the number of binary 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
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$ |