九条可怜最近研究了一下多项式在系数模 意义下的性质。她发现可以用多项式在模 意义下的乘法得到一个很长的字符串：

对于一个 次的系数为 或 的多项式 ，我们在模 意义下计算 ，则 为一个 次的多项式，它有 个系数，将这些系数从高位到低位写下来，就可以得到一个长度为 的 字符串。

例如对于多项式 ，计算 ，这样我们得到了一个长度为 的字符串 。

现在可怜有一个次数为 的多项式 ，整数 以及一个长度为 的 串 。令 为 得到的字符串， 为 的第 个字符到第 个字符，可怜想要知道 在 中出现了多少次。