Fibonacci Strings

题意翻译

### 题意： 定义斐波那契字符串为: $f_1=$"a" $f_2=$"b" $f_n=f_{n-1}+f_{n-2}(n>2)$ 例如，前五项斐波那契字符串为 "a", "b", "ba", "bab", "babba"。 有 $m$ 次询问，第 $i$ 次给出一个字符串 $s_i$，问 $s_i$ 在 $f_n$ 中的出现次数。 ### 输入格式： 第一行包含两个整数 $k$ 和 $m$，斐波那契字符串的数量和查询的数量。 接下来的 $m$ 行包含对应于查询的字符串 $s_i$。保证字符串 $s_i$ 不为空并且仅由字符“a”和“b”组成。 ### 输出格式： 对于每个字符串，$s_i$ 打印它在给定的斐波那契字符串中作为子字符串出现的次数。由于数字足够大，打印模数为 $1e9+7$ ### 数据范围： $m \leq 10^4, \, n \leq 10^{18}, \, \sum|s_i| \leq 10^5$

题目描述

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