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.

斐波那契字符串定义如下：

• $f_1 = \text{``a''}$
• $f_2 = \text{``b''}$
• $f_n = f_{n-1}f_{n-2}$，其中 $n > 2$

因此，前五个斐波那契字符串为："a"、"b"、"ba"、"bab"、"babba"。

给定一个斐波那契字符串以及 $m$ 个字符串 $s_i$。对每个字符串 $s_i$，求其在给定的斐波那契字符串中作为子串出现的次数。

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 ≤ 1018
• 1 ≤ m ≤ 104
• The total length of strings s__i doesn't exceed 105

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.

第一行包含两个以空格分隔的整数 $k$ 和 $m$ —— 分别表示所求的斐波那契字符串的序号以及查询次数。

接下来的 $m$ 行每行包含一个字符串 $s_i$，对应一次查询。保证所有字符串 $s_i$ 非空，且仅由字符 "a" 和 "b" 组成。

获得 30 分的输入限制为：

• $1 \leq k \leq 3000$
• $1 \leq m \leq 3000$
• 所有字符串 $s_i$ 的总长度不超过 $3000$

获得 100 分的输入限制为：

• $1 \leq k \leq 10^{18}$
• $1 \leq m \leq 10^4$
• 所有字符串 $s_i$ 的总长度不超过 $10^5$

请注意：在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin/cout 流，或 %I64d 说明符。

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 (109 + 7). Print the answers for the strings in the order in which they are given in the input.

对于每个字符串 $s_i$，输出其在给定斐波那契字符串中作为子串出现的次数。由于结果可能非常大，请对 $1000000007$（即 $10^9 + 7$）取模后输出。请按照输入中给出字符串的顺序依次输出对应答案。