|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||3||0||0||0.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:
For each dataset, write in one line the remainder of K divided by m.
2 2 100 ab 3 100 ab