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

对于一个 $n$ 次的系数为 $0$ 或 $1$ 的多项式 $f(x)$，我们在模 $2$ 意义下计算 g(x)=f(x)mg(x) = f(x)^mg(x)=f(x)​m​​，则 $g(x)$ 为一个 $nm$ 次的多项式，它有 $nm+1$ 个系数，将这些系数从高位到低位写下来，就可以得到一个长度为 $nm+1$ 的 $01$ 字符串。

例如对于多项式 f(x)=x3+x+1f(x) = x^3 + x + 1f(x)=x​3​​+x+1，计算 g(x)=f(x)3=x9+x7+x6+x5+x2+x+1g(x) = f(x)^3 = x^9 + x^7 + x^6 + x^5 + x^2 + x + 1g(x)=f(x)​3​​=x​9​​+x​7​​+x​6​​+x​5​​+x​2​​+x+1，这样我们得到了一个长度为$10$ 的字符串 $1011100111$。

现在可怜有一个次数为 $n$ 的多项式 $f(x)$，整数 $m,L,R$ 以及一个长度为 $K$ 的 $01$ 串 $t$。令 $s$ 为 f(x)mf(x)^mf(x)​m​​ 得到的字符串，$s[L,R]$ 为$s$ 的第 $L$ 个字符到第 $R$ 个字符，可怜想要知道 $t$ 在 $s[L,R]$ 中出现了多少次。