梅莉和莲子正在观星。莲子发现，若将银河中星星的星等用字母表示，一个星座可以形成一个字符串。
梅莉喜欢重复，因此她取出这个字符串的每个前缀作为子串，统计出了该子串前缀和后缀相同的数量。
莲子不喜欢重复，因此她对于每个子串的答案扣掉了所有前后缀部分有重叠的数量。
她们记下了所有这些前缀的答案加一后的积对 取模的值。可惜秘封俱乐部的活动日志受潮，这个数字不见了踪影。你能帮她们还原出原本的答案吗？
形式化来讲，
求对于字符串 的前 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠的数量。将该数量记作 ，输出所有 的乘积，对 取模的结果即可。