Description

You are given a string.

We define $lcp(i,j)$ as the length of the longest common prefix of the suffix starting at position $i$ of the string and the suffix starting at position $j$.

We define $lcs(i,j)$ as the length of the longest common suffix of the prefix ending at position $i$ of the string and the prefix ending at position $j$.

Now you are given a string of length $n$, and you need to compute

$$\sum_{1\leq i < j \leq n}lcp(i,j)lcs(i,j)[lcp(i,j)\leq k1][lcs(i,j) \leq k2]$$

modulo $2^{64}$ (that is, natural overflow of unsigned long long is sufficient).

$[lcs(i,j) \leq k]$ means that if the proposition $lcs(i,j) \leq k$ is true, then this term equals 1; otherwise it equals 0. The other bracket is defined similarly.

Input Format

The first line contains a string $S$, guaranteed to consist only of lowercase English letters.

The second line contains two positive integers $k1,k2$, representing the constraints in the statement.

Output Format

Output a single positive integer, which is the value of the given expression modulo $2^{64}$.

aabccbbbcbbcbccacbcb
8 20

140

checkcheckcheckonetwo
7 11

216

Hint

Let $n$ denote the length of the string.

Test point 10 is worth 1 point, and for this test point, $n \leq 1000$.

For all test points,

$$1 \leq n \leq 10^5,1\leq k1 , k2 \leq n$$

Translated by ChatGPT 5