Problem H
Message

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$.

Input

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.

Output

For each dataset, output the remainder of $K$ divided by $M$.

2
2 100
ab
3 100
ab

1
52