Fibonacci Strings

题意翻译

**题目描述:** 斐波那契字符串是一个由a,b构成的字符串，第$n$个斐波那契字符串=第$n-1$个斐波那契字符串+第$n-2$个斐波那契字符串。例如前五项斐波那契字符串为：$a$, $b$, $ba$, $bab$, $babba$。 给出$m$个字符串，输出它在第$k$个斐波那契字符串中作为子串的个数。 **输入格式：** 第一行两个整数$k,m$，分别表示有m个字符串以及第k项斐波那契字符串。 接下来m行， 每行一个字符串s。 **输出格式：** 输出m行，每行一个整数，表示字符串s作为子串在第k个斐波那契字符串中出现的次数。 **提示：** 对于30%的数据，1≤$m,k$≤3000。 对于100%的数据，1≤$m$≤$10^{4}$, 1≤$k$≤$10^{18}$。 本题翻译由@[_tommysun_](https://www.luogu.com.cn/user/203452) 提供。

题目描述

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.

输入输出样例

输入样例 #1

6 5
a
b
ab
ba
aba

输出样例 #1

3
5
3
3
1