마테

마테는 부모님에게 영어 소문자로 이루어진 문자열을 선물로 받았다. 이 선물을 조금이라도 써먹으려고, 마테는 다음 곡의 가사에 쓸 각운을 여기에서 찾기로 했다.

각운 하나는 길이가 $D$인 단어이고, 끝에서 두 번째 글자가 $X$, 마지막 글자가 $Y$다. 마테는 주어진 문자열에서 글자를 몇 개 지우고, 지우지 않은 글자를 원래 순서대로 이어 붙여 단어를 만든다. 각운마다 조건을 만족하는 단어를 만드는 방법이 몇 가지인지 구하라.

지운 글자의 위치 집합이 다르면 서로 다른 방법으로 센다.

첫째 줄에 영어 소문자로 이루어진 문자열 $S$가 주어진다. ($2 \le |S| \le 2000$)

둘째 줄에 마테가 찾아야 하는 각운의 개수 $Q$가 주어진다. ($1 \le Q \le 500\,000$)

다음 $Q$개의 줄에는 각각 정수 $D$와 영어 소문자 두 개로 이루어진 문자열 $XY$가 공백으로 구분되어 주어진다. ($2 \le D \le |S|$)

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 각운을 만드는 방법의 수를 출력한다. 이 값이 매우 커질 수 있으므로 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

$S$가 banana이고 $D = 2$, $XY$가 na인 경우를 보자. 글자의 위치는 1부터 센다. 남기는 위치가 $(3, 4)$, $(3, 6)$, $(5, 6)$인 세 가지가 조건을 만족하며, 셋 다 남은 글자를 이어 붙이면 na가 된다. 나머지 글자는 모두 지운다.