Check,Check,Check one two!

您正在听くらげ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$$