2016 ACM ICPC Asia Nha Trang Regional Contest Replay

Start

2017-10-15 12:00 UTC

2016 ACM ICPC Asia Nha Trang Regional Contest Replay

End

2017-10-15 17:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -427 days 13:47:40

Time elapsed

5:00:00

Time remaining

0:00:00

Problem D
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, 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 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.

Output

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