1342: #2252. 「ZJOI2017」多项式

Memory Limit:512 MB Time Limit:3.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

例如对于多项式 f(x)=x3+x+1f(x) = x^3 + x + 1f(x)=x3+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=x9+x7+x6+x5+x2+x+1,这样我们得到了一个长度为101010 的字符串 101110011110111001111011100111

现在可怜有一个次数为 nnn 的多项式 f(x)f(x)f(x),整数 m,L,Rm, L,Rm,L,R 以及一个长度为 KKK010101ttt。令 sssf(x)mf(x)^mf(x)m 得到的字符串,s[L,R]s[L,R]s[L,R]sss 的第 LLL 个字符到第 RRR 个字符,可怜想要知道 ttts[L,R]s[L,R]s[L,R] 中出现了多少次。

输入格式

第一行输入一个整数 TTT 表示数据组数。

每组数据第一行输入五个整数 n,m,K,L,Rn, m,K, L,Rn,m,K,L,R

第二行输入一个长度为 n+1n + 1n+1010101 串表示多项式 f(x)f(x)f(x) 的系数,其中第 iii 位表示 f(x)f(x)f(x) 的第 n−i+1n-i + 1ni+1 次系数。

第三行输入一个长度为 KKK 的字符串表示字符串 ttt

输出格式

对于每组数据输出一个整数表示答案。

样例

样例输入

1
3 3 2 1 10
1011
01

样例输出

2

数据范围与提示

对于100%100\%100% 的数据,保证 1≤T≤51\leq T\leq 51T51≤L≤R≤nm+11\leq L\leq R \leq nm + 11LRnm+1