Count Distinct Substrings

You are given a string ( s ) of length ( n ) and a prime number ( p ). Your task is to compute the number of distinct substrings of ( s ) and output the result modulo ( p ). A substring is defined as a contiguous sequence of characters within ( s ). Note that if a substring appears more than once, it is counted only once.

Formally, for the string ( s ) of length ( n ), consider all substrings ( s[i \ldots j-1] ) with ( 0 \le i < j \le n ). Your goal is to calculate:

[ \text{result} = \left(# { s[i \ldots j-1] : 0 \le i < j \le n } \right) \mod p. ]

Make sure to read the input from standard input and write the output to standard output.

inputFormat

The input consists of two lines. The first line contains two integers ( n ) and ( p ), where ( n ) is the length of the string and ( p ) is a prime modulus. The second line contains the string ( s ) consisting of lowercase English letters.

outputFormat

Output a single integer representing the number of distinct substrings of ( s ) modulo ( p ).## sample

4 1000000007
abcd

10