메시지

어떤 학생이 친구에게 메시지를 보내려고 한다. 메시지는 알파벳 소문자로만 이루어진 문자열 $p$이다. 메시지를 암호화하기 위해 학생은 $p$를 부분 문자열로 포함하는 길이 $n$의 소문자 알파벳 문자열 $h$를 만든다. 학생은 이런 문자열 $h$를 만드는 서로 다른 방법의 수가 얼마인지 궁금해한다.

양의 정수 $n$, $m$과 알파벳 소문자로만 이루어진 문자열 $p$가 주어질 때, $p$를 부분 문자열로 포함하는 길이 $n$의 소문자 알파벳 문자열 $h$를 만드는 서로 다른 방법의 수를 $K$라고 하자. $K$를 $m$으로 나눈 나머지를 구하라.

입력은 여러 개의 데이터셋으로 이루어진다. 첫째 줄에는 데이터셋의 개수가 주어지며, 이는 양의 정수이고 20 이하이다. 다음 줄부터 데이터셋이 주어진다.

각 데이터셋은 다음과 같이 이루어진다.

• 첫째 줄에 두 양의 정수 $n$, $m$이 주어진다. ($n \le 10^{12}$; $m \le 10^{12}$)
• 다음 줄에 알파벳 소문자가 최대 50개인 문자열 $p$가 주어진다.

각 데이터셋에 대해 $K$를 $m$으로 나눈 나머지를 한 줄에 출력한다.