Fibonacci strings are defined as follows:

f₁ = «a»
f₂ = «b»
f_n = f_n - 1 f_n - 2, n > 2

Thus, the first five Fibonacci strings are: "a", "b", "ba", "bab", "babba".

You are given a Fibonacci string and m strings s_i. For each string s_i, find the number of times it occurs in the given Fibonacci string as a substring.

Input

The first line contains two space-separated integers k and m — the number of a Fibonacci string and the number of queries, correspondingly.

Next m lines contain strings s_i that correspond to the queries. It is guaranteed that strings s_i aren't empty and consist only of characters "a" and "b".

The input limitations for getting 30 points are:

1 ≤ k ≤ 3000
1 ≤ m ≤ 3000
The total length of strings s_i doesn't exceed 3000

The input limitations for getting 100 points are:

1 ≤ k ≤ 10¹⁸
1 ≤ m ≤ 10⁴
The total length of strings s_i doesn't exceed 10⁵

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Output

For each string s_i print the number of times it occurs in the given Fibonacci string as a substring. Since the numbers can be large enough, print them modulo 1000000007 (10⁹ + 7). Print the answers for the strings in the order in which they are given in the input.

Fibonacci Strings

Examples