Polynomial Exponentiation and Substring Occurrence

Given a polynomial \( f(x) \) of degree \( n \) with coefficients in \( \{0,1\} \) (represented as a binary string of length \( n+1 \) with the highest degree coefficient first), define \( g(x) = f(x)^m \) under arithmetic modulo 2. Note that \( g(x) \) is a polynomial of degree \( nm \) and has \( nm+1 \) coefficients. By writing these coefficients from the highest degree to the constant term, we obtain a binary string \( s \) of length \( nm+1 \).

You are given the integers \( n, m, L, R \), the binary string representing \( f(x) \) and another binary string \( t \) (of length \( K \)). Let \( s[L, R] \) denote the substring of \( s \) from the \( L\textsuperscript{th} \) character to the \( R\textsuperscript{th} \) character (1-indexed). Your task is to compute the number of (possibly overlapping) occurrences of \( t \) in \( s[L, R] \).

For example, if \( f(x)=x^3+x+1 \) (represented as 1011) and \( m=3 \), then \[ g(x)=f(x)^3=x^9+x^7+x^6+x^5+x^2+x+1, \] so \( s=1011100111 \) (of length 10). If \( L=1, R=10 \) and \( t=101 \), the answer is 1.

inputFormat

The input consists of three lines:

1. The first line contains four integers \( n, m, L, R \) where \( n \) is the degree of the polynomial, \( m \) is the exponent, and \( L, R \) specify the range for the substring (1-indexed) of \( s \).
2. The second line contains a binary string of length \( n+1 \) representing \( f(x) \) (the first character corresponds to the coefficient of \( x^n \)).
3. The third line contains a binary string \( t \).

outputFormat

Output a single integer representing the number of occurrences (possibly overlapping) of \( t \) in the substring \( s[L, R] \) of the binary string \( s \) derived from \( f(x)^m \).

sample

3 3 1 10
1011
101

1