문자열 - 그래프 매칭

다음과 같은 방식으로 알파벳 소문자로 이루어진 문자열을 이용해 그래프를 만들 수 있다.

1. 알파벳 소문자 a부터 z까지에 대응되는 정점을 만든다.
2. 길이가 $L$인 문자열 $S$를 $S_1S_2S_3\cdots S_L$로 나타낸다. $L-1$ 이하인 모든 양의 정수 $i$에 대해 $S_i \to S_{i+1}$인 간선을 그래프에 추가한다. 같은 간선이 여러 번 추가될 경우에는 한 번만 추가한다.

알파벳 소문자에 대응되는 정점들로 이루어진 그래프와 문자열 $T$가 주어졌을 때, 위 변환 과정을 거쳐 주어진 그래프와 동일한 그래프가 만들어지는 $T$의 부분 문자열의 개수를 구하시오.

부분 문자열은 문자열의 앞과 뒤에서 원하는 길이만큼 잘라내어 얻을 수 있는 길이 $1$ 이상의 문자열이다. 예를 들어 abcde에서 cd와 abc는 부분 문자열이지만, bd는 앞뒤 어떤 길이로 잘라내도 얻을 수 없으므로 부분 문자열이 아니다.

첫 번째 줄에 문자열의 길이를 나타내는 정수 $N$이 주어진다. ($2 \le N \le 2\,000\,000$)

두 번째 줄에 알파벳 소문자로만 이루어진 길이 $N$의 문자열 $T$가 주어진다.

세 번째 줄에 그래프의 간선 개수를 나타내는 정수 $M$이 주어진다. ($1 \le M \le 26^2$)

네 번째 줄부터 $M+3$번째 줄까지 간선을 나타내는 알파벳 소문자 2개가 공백 없이 주어진다. $x_iy_i$가 주어진 줄은 $x_i \to y_i$인 방향 간선을 뜻한다. $x_i$와 $y_i$는 같은 문자일 수 있다. 같은 간선이 여러 번 주어지지 않는다.

위 변환 과정을 거쳤을 때 주어진 그래프와 동일한 그래프가 만들어지는 $T$의 부분 문자열 개수를 첫 번째 줄에 출력한다.