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$ and $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 several 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 contains two positive integers $n$ and $M$, where $n \leq {10}^{12}$ and $M \leq {10}^{12})$;
The next line contains the text string $p$ consisting of at most $50$ lowercase latin alphabet letters.
For each dataset, output the remainder of $K$ divided by $M$.
Sample Input 1 | Sample Output 1 |
---|---|
2 2 100 ab 3 100 ab |
1 52 |