CF177G2 Fibonacci Strings

Fibonacci strings are defined as follows: - $ f_{1} $ = «a» - $ f_{2} $ = «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.

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

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^{9}+7) $ . Print the answers for the strings in the order in which they are given in the input.