시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 8 | 1 | 1 | 20.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
1 52
ICPC > Regionals > Asia Pacific > Vietnam > 2016 Nha Trang Regional Contest D번