말썽꾸러기 캥거루 새끼

캥거루 단어란 자신의 동의어(즉, ``새끼'')를 품고 있는 단어로, 그 동의어의 모든 글자가 같은 순서로 단어 안에 등장한다. 예를 들어, pastej은 동의어 paj(**pa**ste**j**)를 품고 있으므로 캥거루 단어이다. 또한 aste과 atj이 단어라고 가정하면 이들도 새끼로 인정되지만, paaj이나 etsa은 인정되지 않는다. 형식적으로 말하면, 새끼는 단어의 부분 수열이어야 한다.

더 나아가, 새끼가 단어 안에 서로 다른 두 가지 방식으로 들어갈 수 있으면 그 새끼를 말썽꾸러기라고 한다. paj은 말썽꾸러기 새끼가 아니지만, 원래 단어가 paastej이었다면 말썽꾸러기 새끼였을 것이다 -- 그 경우 **pa**aste**j** 또는 **p**a**a**ste**j**으로 숨을 수 있었기 때문이다.

(지어낸) 단어 $S$과 (지어낸) 동의어 목록이 주어질 때, 동의어 중 몇 개가 $S$의 말썽꾸러기 새끼인지 구하여라.

채점

여러 테스트 케이스 그룹을 통해 제출한 풀이를 테스트한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한 조건

$1$ |$20$| $N, M, K \le 100$.

$2$ |$20$| $N, M \le 1000$, 그리고 모든 새끼는 말썽꾸러기 새끼이다.

$3$ |$20$| $N, M \le 1000$.

$4$ |$20$| 모든 새끼는 말썽꾸러기 새끼이다.

$5$ |$20$| 추가 제한 조건이 없다.

예제

예제 1에서는 처음 세 단어가 $S$의 새끼이며, 또한 말썽꾸러기이다. 따라서 이 테스트 케이스는 테스트 그룹 2 또는 4에 포함될 수 있다.

예제 2에서는 처음 네 단어가 새끼이며, 그중 처음 두 단어는 말썽꾸러기 새끼이기도 하다. 이 테스트 케이스는 테스트 그룹 2 또는 4에 포함될 수 없다.

• 첫 번째 줄에는 문자 a-z로 이루어진 비어 있지 않은 문자열, 즉 확인하려는 단어 $S$가 주어진다.

• 두 번째 줄에는 단어의 동의어 수를 나타내는 정수 $N$ ($1 \le N \le 100\,000$)이 주어진다.

• 다음 $N$개의 줄에는 동의어가 하나씩 주어지며, 각각은 문자 a-z로 이루어진 비어 있지 않은 문자열이다.

어떤 동의어도 두 번 등장하거나 $S$과 같지 않다.

$M$을 $S$의 글자 수, $K$를 동의어들의 글자 수의 합이라고 하자. 그러면 $M \le 100\,000$, $K \le 500\,000$가 성립한다.

정수 하나, 즉 $S$의 말썽꾸러기 새끼인 단어의 수를 출력한다.