13203번 - 읽어내기

문제

고대 유적을 발굴하던 성원이는 커다란 비석을 찾아내었고, 학계에 보고하기 위해 그 비석에 적힌 글을 해독하고 있다. 하지만 이 비석은 오랜 세월을 거치며 글자들이 지워져 잘 보이지 않게 되었다.

이 비석이 만들어질 당시의 사람들은 비석에 왕의 이름을 써 놓는 것을 좋아했다. 비석의 글자들 중 일부 (연속하지 않아도 된다)를 골라 순서대로 조합하여 왕의 이름이 되는 경우의 수가 많을수록 더 좋아했다고 한다. 또 이 당시 사람들은 말을 길게 하는 것을 좋아하지 않아 왕의 이름은 항상 5글자 이내였다고 한다.

방사선 연대 측정을 통해 이 비석이 묻힐 당시의 왕의 이름을 알게 된 성원이는 이 비석에 왕의 이름을 읽어낼 수 있는 경우의 수가 몇 가지인지 알고 싶게 되었다. 그런데 비석의 글씨는 잘 보이지 않으므로 연구가 진행됨에 따라 비석의 일부의 해석이 달라질 수 있고, 그 때마다 이름을 읽어내는 경우의 수를 알고 싶어한다. 성원이를 도와 경우의 수를 계산하는 프로그램을 작성해 주자.

입력

첫 번째 줄에 테스트 케이스의 수 T 가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 비석의 글자 수 N(1 ≤ N ≤ 200, 000)과 왕의 이름의 길이 M(1 ≤ M ≤ 5), 그리고 비석의 해석이 바뀌는 횟수 Q(0 ≤ Q ≤ 100, 000)가 주어진다. 둘째 줄에는 비석에 적힌 글의 첫 번째 해석이 하나의 문자열로 주어진다. 이는 영어 알파벳 대문자로만 구성되어 있다. 셋째 줄에는 왕의 이름이 하나의 문자열로 주어지며, 마찬가지로 영어 알파벳 대문자로만 구성되어 있다. 넷째 줄부터 Q개의 줄에는 한 줄마다 두 개의 정수 A_i , B_i 와 문자열 S_i 가 주어진다. (1 ≤ A_i ≤ B_i ≤ N, len(S_i) = B_i − A_i + 1) 이는 비석의 A_i 번째 문자부터 B_i 번째 문자까지의 해석이 S_i 로 바뀐다는 뜻이다. S_i 의 길이 총합은 2, 000, 000 이하이다.

출력

각 테스트 케이스마다, Q + 1개의 줄에 한 줄에 하나의 정수를 출력한다. i번째 줄에는 비석의 i번째 해석에서 왕의 이름을 읽을 수 있는 경우의 수를 출력한다. 답이 커질 수 있으므로 1, 000, 000, 007로 나눈 나머지를 출력한다.

제한

힌트