문자열 복원

네트워크 검색이나 게놈 해독 같은 여러 응용 문제에서는 문자열에 대한 여러 작업을 수행해야 한다. 예를 들어, 문자열에 대한 일부 정보를 가지고 문자열 자체를 복원해야 하는 경우가 자주 있다.

두 문자열 S1과 S2가 주어진다. 이 중 하나는 찾고자 하는 문자열 S의 접미사이고, 다른 하나는 접두사라는 사실이 알려져 있다. 또한 찾고자 하는 문자열의 길이 L과 문자열 S가 라틴 알파벳 소문자로만 구성되어 있다는 사실도 알려져 있다.

이러한 조건을 만족하는 문자열의 개수를 구해야 한다. 이 수가 매우 클 수 있으므로 m으로 나눈 나머지를 출력해야 한다.

첫 번째 줄에는 처리해야 할 입력 데이터 집합의 개수를 나타내는 정수 t (1 ≤ t ≤ 100)가 주어진다.

각 입력 데이터 집합은 세 줄로 구성된다. 첫 번째 줄에는 두 정수 L과 m (1 ≤ L ≤ 10^9, 1 ≤ m ≤ 10^4)이 주어진다. 두 번째와 세 번째 줄에는 각각 문자열 S1과 S2가 주어진다. 이들은 비어 있지 않고 라틴 알파벳 소문자로만 구성되며, 길이는 200자를 넘지 않는다.

각 입력 데이터 집합에 대해, 조건을 만족하는 문자열의 개수를 m으로 나눈 나머지를 한 줄에 출력한다.