#P4175. [2015年湖南省队省队集训]小G的电话本
[2015年湖南省队省队集训]小G的电话本
[2015 湖南省队集训] 小 G 的电话本
题目描述
小 G 的电话本里有一个名字 ,托尼想统计它的片段。一个片段是从 中选出的一个非空连续子串,由它的起止位置唯一确定。内容相同但位于不同位置的片段是不同的片段。
对于一个片段 ,记 为它的内容在 中出现的次数。每个不同的出现位置都计入,包括相互重叠的出现。
求满足 的有序 元组 的数量。同一片段可以在一个元组中选多次;只要某一项选取的片段位置不同,两个元组就不同。
输入格式
第一行两个整数 。第二行给出名字 。令 为 的长度,满足 ,。
输出格式
输出一行一个整数,表示方案数对 的非负余数。
样例 #1
样例输入 #1
3 4
aaaaa
样例输出 #1
6
样例说明
字符串有两处内容为 的片段,分别从第 、 个位置开始;它们的出现次数都是 。完整字符串 的出现次数是 。任意选择这两处短片段之一放入元组的任一项,另外两项都选完整字符串。答案为 。