← 返回题目列表

Codeforces · 177/G2

G2. 斐波那契字符串

中文机器翻译题面 查看原题

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

- f1 = «a»
- f2 = «b»
- fn = fn - 1 fn - 2,n > 2

因此,前五个斐波那契字符串是:“a”、“b”、“ba”、“bab”、“babba”。

给你一个斐波那契字符串和 m 个字符串 si。对于每个字符串 si,查找它作为子字符串在给定斐波那契字符串中出现的次数。

输入

第一行包含两个空格分隔的整数 k 和 m — 相应地,斐波那契字符串的数量和查询的数量。

接下来的 m 行包含与查询相对应的字符串 si 。保证字符串 si 不为空并且仅由字符“a”和“b”组成。

获得 30 点的输入限制为:

- 1 ≤ k ≤ 3000
- 1 ≤ 米 ≤ 3000
- 字符串si的总长度不超过3000

获得 100 点的输入限制为:

- 1 ≤ k ≤ 1018
- 1 ≤ 米 ≤ 104
- 字符串si的总长度不超过105

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

输出

对于每个字符串,打印它作为子字符串在给定斐波那契字符串中出现的次数。由于数字可能足够大,因此打印它们对 1000000007 (109 + 7) 取模。按照输入中给出的顺序打印字符串的答案。

示例

输入 #1

6 5
a
b
ab
ba
aba

输出 #1

3
5
3
3
1