CF177G2 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, \, k \leq 10^{18}, \, \sum|s_i| \leq 10^5$