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 ≤ 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 18 1 ≤ m ≤ 10 4 The total length of strings s i doesn't exceed 10 5 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. 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.