斐波那契字符串定义如下:
- 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