Chef buys a new restaurant. At his new restaurant, he calls his rival chef named 'Code'. Also he places all his dishes on N different tables in
such a order that, the
first table contains dish "a" and second one contains dish "b". From next table onwards dishes are arranged in such a way that, the dish on the given
table is the mixture of the
previous two table's dishes, i.e., the dishes on table 1, 2, 3, 4, 5, 6 will be "a", "b", "ba", "bab", "babba", "babbabab" respectively and so on.
Code goes to Kth table and performs m queries on the dish at that table to annoy chef.
On each query he picks up a different section si of the dish and asks chef, the number of occurrences of si in the given dish.

 

Input

• The first line contains two space-separated integers K and m denoting the table number and the number of queries, correspondingly.
• Next m lines contain sections si that correspond to the queries. It is guaranteed that section si isn't empty and consist only of
  characters "a" and "b".

Output

• For each section si print the number of times it occurs in the dish on the given table. Since the numbers can be large enough, print them
  modulo 1000000007 (10^9+7). Print the answers for

  the section in the order in which they are given in the input.

Constraints

• 1 K 1018
• 2 m 104
• The total length of strings si doesn't exceed 10^5

Example

Input: 6 5 a b ab ba aba Output: 3 5 3 3 1 Input: 10 10 bb ab ba aa bb ab ba aa bb ab Output: 12 21 21 0 12 21 21 0 12 21

Explanation

Case 1 : Code goes to table number
6, which contain babbabab as the dish. Section 'ba' has occurred 3 times in the given dish. Similarly aba has occured once in the given dish.