지저분한 캥거루 새끼

캥거루 단어는 자기 자신의 동의어(이하 "새끼")를 품고 있는 단어다. 새끼의 모든 글자가 단어 안에 같은 순서로 나타나야 한다. 예를 들어 pastej는 동의어 paj를 품고 있으므로 캥거루 단어다(pastej). aste와 atj도 단어라고 가정하면 새끼로 쳐주지만, paaj나 etsa는 아니다. 형식적으로 말하면 새끼는 단어의 부분 수열이어야 한다.

새끼가 단어 안에 두 가지 서로 다른 방식으로 들어갈 수 있으면 그 새끼를 지저분하다고 한다. paj는 지저분한 새끼가 아니지만, 원래 단어가 paastej였다면 지저분한 새끼가 된다. paastej 또는 paastej로 숨을 수 있기 때문이다.

(가상의) 단어 $S$와 (가상의) 동의어 목록이 주어질 때, 동의어 중 몇 개가 $S$의 지저분한 새끼인가?

• 첫째 줄에는 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$의 지저분한 새끼인 단어의 개수를 정수로 출력한다.

예제 1에서 처음 세 단어는 $S$의 새끼이며, 게다가 지저분하다. 따라서 이 테스트 케이스는 테스트 그룹 2나 4에 포함될 수 있다.

예제 2에서 처음 네 단어는 새끼이고, 그중 처음 두 단어는 지저분한 새끼다. 이 테스트 케이스는 테스트 그룹 2나 4에 포함될 수 없다.