비석 읽어내기

고대 유적을 발굴하던 성원이가 커다란 비석을 찾아냈다. 학계에 보고하려고 비석에 새겨진 글을 해독하는 중인데, 오랜 세월을 지나며 글자가 지워져 잘 보이지 않는다.

비석을 세우던 시절 사람들은 비석에 왕의 이름을 새겨 넣기를 좋아했다. 비석의 글자 중 일부를 골라(연속하지 않아도 된다) 순서대로 이었을 때 왕의 이름이 되는 경우의 수가 많을수록 좋은 비석으로 쳤다. 또 말을 길게 하는 것을 싫어해서 왕의 이름은 언제나 5글자 이내였다.

연대 측정으로 비석이 묻히던 당시의 왕 이름을 알아낸 성원이는, 이 비석에서 왕의 이름을 읽어낼 수 있는 경우의 수가 몇 가지인지 알고 싶다. 글씨가 흐릿해서 연구가 진행되면 비석 일부의 해석이 바뀌고, 해석이 바뀔 때마다 경우의 수를 다시 알고 싶어 한다. 성원이를 도와 경우의 수를 계산하는 프로그램을 작성하자.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 10$)가 주어진다.

각 테스트 케이스의 첫 줄에는 비석의 글자 수 $N$ ($1 \le N \le 200000$), 왕 이름의 길이 $M$ ($1 \le M \le 5$), 비석의 해석이 바뀌는 횟수 $Q$ ($0 \le Q \le 100000$)가 주어진다. 둘째 줄에는 비석에 적힌 글의 첫 번째 해석이 문자열 하나로 주어지며, 영어 대문자로만 이루어져 있다. 셋째 줄에는 왕의 이름이 문자열 하나로 주어지고, 역시 영어 대문자로만 이루어져 있다.

이어지는 $Q$개의 줄에는 한 줄마다 두 정수 $A_i$, $B_i$와 문자열 $S_i$가 주어진다 ($1 \le A_i \le B_i \le N$, $S_i$의 길이는 $B_i - A_i + 1$). 비석의 $A_i$번째 글자부터 $B_i$번째 글자까지의 해석이 $S_i$로 바뀐다는 뜻이다. $S_i$도 영어 대문자로만 이루어져 있고, 모든 테스트 케이스에 걸친 $S_i$의 길이 합은 2000000 이하이다.

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