전 우주 생명 게놈 데이터베이스 리턴즈

서기 2301년, 우주연방공화국 생명과학국에서는 우주 생물의 게놈 서열을 연구하고 있었다. 최근 연구에 따르면 게놈 서열 안에 특정 패턴이 몇 번 나타나는지가 생물의 성질에 큰 영향을 준다.

우주 생물의 게놈 서열은 영문 대문자로 이루어진 문자열로 표현된다. 연구원들은 게놈 서열에서 특정 패턴이 몇 번 나타나는지 세려고 한다. 다만 게놈 서열이 매우 길어서, 아래 방법으로 반복되는 부분 문자열을 압축해 데이터베이스에 저장한다.

이 문제의 목표는 압축된 게놈 서열 $S$에서 문자열 $Q$가 몇 번 나타나는지 세는 프로그램을 작성하는 것이다. $Q$의 출현은 시작 위치만 다르면 겹치는 부분이 있어도 서로 다른 출현으로 센다. 예를 들어 MISSISSIPPI에서 ISSI는 2번 나타난다.

압축 규칙은 다음 BNF로 정의된다.

<Genome> ::= <Letter> | <Number> <Letter> | <Number> ( <Genome> ) | <Genome> <Genome>
<Letter> ::= 'A' | 'B' | ... | 'Z'
<Number> ::= <Digit> | <Number> '0' | <Number> <Digit>
<Digit> ::= '1' | '2' | ... | '9'

정수는 바로 뒤에 오는 문자열을 그 횟수만큼 반복한다는 뜻이다. 예를 들어 5A는 AAAAA, 2(AB)는 ABAB를 뜻한다. 정수 바로 뒤에 괄호가 없으면 그 뒤의 한 글자만 반복된다. 예를 들어 2AB는 AAB를 뜻한다. 반복은 여러 겹으로 중첩될 수 있다. 2(2(AB)C)는 2(ABABC)와 같으며, ABABCABABC를 뜻한다.

입력은 최대 50개의 데이터셋으로 구성된다. 각 데이터셋은 다음 형식으로 주어진다.

S
Q

첫 줄은 압축된 게놈 서열 $S$이다. $S$는 위의 BNF를 따르며, 길이는 1 이상 3000 이하이다. $S$를 펼친 게놈 서열의 길이는 $10^{18}$ 이하이다. 둘째 줄은 찾을 문자열 $Q$이다. $Q$는 영문 대문자로 이루어지며, 길이는 1 이상 3000 이하이다.

입력의 끝은 '#' 한 글자만 있는 줄로 나타낸다.

각 데이터셋에 대해 $S$를 펼친 문자열에 $Q$가 몇 번 나타나는지 출력하라.