Distinct Fixed-Length Substrings

You are given a string s of length n consisting of lowercase English letters, and two integers l and base. Your task is to count the number of distinct contiguous substrings of s of length l.

A substring is defined by a continuous segment of characters in s. Two substrings are considered different if there exists at least one position in which their characters differ.

A common approach to solve this problem is to use a rolling hash algorithm. In this problem, you are required to use the following modulus and to compute hash values as follows:

$$\text{MOD} = 10^9+7$$

For a substring of length l, its hash value is calculated using the formula:

$$\text{{hash}} = (\cdots(((s[0]-'a')\times base + (s[1]-'a')) \times base + \cdots + (s[l-1]-'a')) \bmod\, \text{{MOD}}. $$

Moreover, when moving the sliding window one step to the right, you should update the hash value by multiplying the previous hash by base, adding the new character and subtracting the contribution of the character leaving the window (which is multiplied by $$base^l \bmod, \text{{MOD}}$$).

If l is greater than n, the answer is 0.

inputFormat

The first line contains three integers n, l, and base, where n is the length of the string s, l is the required substring length, and base is the base used for rolling hash computations.

The second line contains the string s consisting of n lowercase English letters.

outputFormat

Output a single integer: the number of distinct contiguous substrings of s that are of length l.

sample

5 2 31
ababa

2