一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串 $P$ 是串 $A$ 的前缀, 当且仅当存在串 $B$ , 使得 $A=PB$. 如果 $P\ne A$ 并且 $P$ 不是一个空串,那么我们说 $P$ 是 $A$ 的一个 $proper$ 前缀. 定义 $Q$ 是 $A$ 的周期, 当且仅当 $Q$ 是 $A$ 的一个 $proper$ 前缀并且 $A$ 是 $QQ$ 的前缀(不一定要是 $proper$ 前缀).

比如串 $abab$ 和 $ababab$ 都是串 $abababa$ 的周期. 串 $A$ 的最大周期就是它最长的一个周期或者是一个空串(当 $A$ 没有周期的时候), 比如说, $ababab$ 的最大周期是 $abab$ . 串 $abc$ 的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.

阿申准备报名参加 $GT$ 考试，准考证号为 $n$ 位数 $X_1{X}_2\cdots X_n(0\le X_i\le 9)$，他不希望准考证号上出现不吉利的数字。

他的不吉利数字 $A_1{A}_2\cdots A_m(0\le A_i\le 9)$ 有 $m$ 位，不出现是指 $X_1{X}_2\cdots X_n$ 中没有恰好一段等于 $A_1{A}_2\cdots A_m$，$A_1$​ 和 $X_1$ 可以为 $0$。

阿申想知道不出现不吉利数字的号码有多少种，输出模 $K$ 取余的结果。

给定一个字符串 $S$ ，求出 $num$ 数组——对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 $num[i]$ 。

特别地，为了避免大量的输出，你不需要输出 $num[i]$ 分别是多少，你只需要输出所有 $(num[i]+1)$ 的乘积，对 ${10}^9+7$ 取模的结果即可。