Giải bài trực tuyến

The VNOI King is very interested in computer science and arts. He is especially interested in the binary palindrome strings. A binary palindrome string is a string of only two characters 0, 1 and can be read the same way in either direction.

In the King's 101^th birthday, he announced a list of K binary strings for his courtiers. He then issued a question: how many binary strings are there that satisfies both the following two conditions:

• It is a binary palindrome string of exactly N characters.
• It does not contain two non-overlapped substrings in the given list of K binary strings.

For example, if the King's list consists of two binary strings 101 and 1001, two binary strings that do not satisfy the second condition are: 1011001 (containing two strings 101 and 1001), 1010101 (the two substrings can be the same). Two binary strings that satisfy the second condition are: 1001001 (two substrings 1001 are overlapped), 1010011.

Please help the courtiers answer the King's question!

Input

• The first line contains two integers N and K.
• Each line in the next K lines contains a binary string in the King's list of binary strings.

Output

• The number of binary strings satisfying the above two conditions. You only need to print the remainder of the result when dividing by 1000000007.

Example

Input:

5 1
0


Output:

2

Output details

• There are 2³ = 8 binary palindrome strings of length 5. Since the string cannot have 2 characters 0, there are only 2 strings which meet the given conditions: 11111 and 11011.

   

Constraints

• 1 ≤ N ≤ 300.
• 0 ≤ K ≤ 30.
• Each string in the input has its length not exceeding 30.
• In 30% of the test cases, N does not exceed 30.