A student wants to send to his friend a message, which is a text string $p$ consisting of only lowercase latin alphabet letters. To encrypt his message, he creates a lowercase alphabet string $h$ of size $n$ that contains $p$ as a substring. The student is curious to find out how many different ways there are to create such a string $h$.
Given two positive integers $n, M$ and a string $p$ consisting of only lowercase latin alphabet letters, letâ€™s denote $K$ to be the total number of different ways to create a lowercase alphabet string $h$ of size $n$ such that $p$ is a substring of $h$. Your task is to find the remainder of $K$ divided by $M$.
The input consists of serveral datasets. The first line of the input contains the number of datasets which is a positive integer and is not greater than $20$. The following lines describe the datasets.
Each dataset is described by the following lines:
The first line conatins two positive integers $n, M (n \leq {10}^{12}; M \leq {10}^{12})$;
The next line contains the text string $p$ consisting of at most $50$ lowercase latin alphabet letters.
For each dataset, write in one line the remainder of $K$ divided by $M$.
Sample Input 1 | Sample Output 1 |
---|---|
2 2 100 ab 3 100 ab |
1 52 |