You are given positive integers , and a string of length consisting of lowercase English letters.
Let be the string obtained by concatenating copies of .
Find the inversion number of the Suffix Array of , modulo .
For a string of length , the suffix array of is a permutation of integers from to that represents the starting positions of all non-empty suffixes of , sorted in lexicographical order.
输入格式
The input is given in the following format:
is a string of length consisting of lowercase English letters.
