题目背景

您正在听くらげP的チェチェ・チェック・ワンツー!，突然教导主任推门进来了，于是您只好假装自己在写字符串题。

（结果教导主任一眼秒了这水题，您因没事刷水题被批判了一番）

题目描述

给定一个字符串，

我们定义 $\operatorname{lcp}(i,j)$ 表示从字符串第 $i$ 个位置开始的后缀和从第 $j$ 个位置开始的后缀的最长公共前缀长度，

我们定义 $\operatorname{lcs}(i,j)$ 表示在字符串第 $i$ 个位置结束的前缀和在第 $j$ 个位置结束的前缀的最长公共后缀长度。

现在给定一个长度为 $n$ 的字符串，希望您求出

$$\sum_{1\leq i < j \leq n}\operatorname{lcp}(i,j)\operatorname{lcs}(i,j)[\operatorname{lcp}(i,j)\leq k_1][\operatorname{lcs}(i,j) \leq k_2]$$

模 $2^{64}$ 的值（也就是 unsigned long long 自然溢出即可）。

$[\operatorname{lcs}(i,j) \leq k]$ 表示如果 $\operatorname{lcs}(i,j) \leq k$ 这个命题为真那么这个式子的值是 $1$ 否则是 $0$，另外一个方括号也是同理。

输入格式

第一行一个字符串 $S$，保证仅含有小写的英文字母。

第二行两个正整数 $k_1,k_2$ 表示题目中的限制条件。

输出格式

仅一行一个正整数，表示题目中所给式子模 $2^{64}$ 的值。

aabccbbbcbbcbccacbcb
8 20

140

checkcheckcheckonetwo
7 11

216

提示

设 $n$ 表示字符串的长度。

测试点 $10$ 的分值为 $1$，这个测试点的 $n \leq 1000$。

对于所有的测试点，$1 \leq n \leq 10^5,1\leq k_1 , k_2 \leq n$。