CF177G1 Fibonacci Strings

斐波那契字符串是一个由a,b构成的字符串，第$n$个斐波那契字符串=第$n-1$个斐波那契字符串+第$n-2$个斐波那契字符串。例如前五项斐波那契字符串为：$a$, $b$, $ba$, $bab$, $babba$。 给出$m$个字符串，输出它在第$k$个斐波那契字符串中作为子串的个数。

第一行两个整数$k,m$，分别表示有m个字符串以及第k项斐波那契字符串。 接下来m行， 每行一个字符串s。

输出m行，每行一个整数，表示字符串s作为子串在第k个斐波那契字符串中出现的次数。

对于30%的数据，1≤$m,k$≤3000。 对于100%的数据，1≤$m$≤$10^{4}$, 1≤$k$≤$10^{18}$。 本题翻译由@[_tommysun_](https://www.luogu.com.cn/user/203452) 提供。