Problem Background

You are listening to くらげP's "チェチェ・チェック・ワンツー!" when the教导主任 suddenly enters the room. You quickly pretend to be working on a string problem.

(The教导主任 instantly recognizes this as an easy problem and criticizes you for wasting time on trivial tasks.)

Problem Description

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

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

For a given string of length $n$, you are required to compute the following:

$$\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}$ (which means using unsigned long long and allowing natural overflow).

The notation $[lcs(i,j) \leq k]$ evaluates to 1 if the condition $lcs(i,j) \leq k$ is true, otherwise it evaluates to 0. The same applies to the other bracketed condition.

Input Format

The first line contains a string $S$, consisting only of lowercase English letters.

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

Output Format

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

Sample Input and Output

Sample Input #1

aabccbbbcbbcbccacbcb
8 20

Sample Output #1

140

Sample Input #2

checkcheckcheckonetwo
7 11

Sample Output #2

216

Notes

Let $n$ denote the length of the string.

The score for test case 10 is 1, where $n \leq 1000$.

For all test cases,

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

见题面 Input 部分

见题面 Output 部分