题目背景

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

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

题目描述

给定一个字符串

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

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

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

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

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

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

输入格式

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

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

输出格式

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

aabccbbbcbbcbccacbcb
8 20

140

checkcheckcheckonetwo
7 11

216

提示

设n表示字符串的长度

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

对于所有的测试点

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