시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB81120.000%

문제

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 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, m (n ≤ 1012; m ≤ 1012);
  • 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.

예제 입력 1

2
2 100
ab
3 100
ab

예제 출력 1

1
52

출처

ICPC > Regionals > Asia Pacific > Vietnam > 2016 Nha Trang Regional Contest D번

  • 문제의 오타를 찾은 사람: eric00513