접힌 생산 지시서

문제

한 공장에는 A형 부품과 B형 부품을 만드는 생산 라인이 있다. 운영자는 같은 작업을 여러 번 적는 수고를 줄이기 위해 반복 작업을 괄호로 접어서 표현한다. 생산 장치는 이 지시서를 재귀적으로 해석하며, 괄호 안에 또 다른 반복 작업이 들어 있어도 같은 규칙을 적용한다. 지시서에서 문자 A는 A형 부품 한 개를 생산하라는 뜻이고, 문자 B는 B형 부품 한 개를 생산하라는 뜻이다. 여러 작업을 붙여 쓰면 왼쪽부터 차례대로 모두 수행한다. 숫자 d 바로 뒤에 괄호로 묶인 지시서가 나오면 괄호 안의 작업 전체를 d번 반복한다. 여기서 d는 2부터 9까지의 한 자리 정수이다. 숫자는 반드시 여는 괄호 바로 앞에만 나오며, 숫자 하나와 괄호 한 쌍이 하나의 반복 작업을 이룬다. 지시서는 하나 이상의 작업을 이어 붙여 만든다. 각 작업은 A, B 또는 d(P) 형태 중 하나이며, P 역시 하나 이상의 작업으로 이루어진 올바른 지시서이다. 빈 괄호는 없고, 여는 괄호와 닫는 괄호는 항상 올바르게 짝지어진다. 공백이나 줄바꿈은 지시서 안에 들어 있지 않다. 반복 작업이 중첩되는 깊이에는 지시서 길이에서 정해지는 한계 외에 별도의 제한이 없다. 괄호를 모두 풀어 쓴 결과는 원래 지시서보다 훨씬 길어질 수 있다. 공장은 작업의 실제 실행 순서를 출력하려는 것이 아니라, 전체 작업을 마쳤을 때 생산되는 두 종류의 부품 수만 확인하려고 한다. 주어진 지시서에 따라 생산되는 A형 부품 수와 B형 부품 수를 각각 구한다. 두 수가 매우 클 수 있으므로 각 수를 1,000,000,007로 나눈 나머지를 출력한다. 어떤 종류의 부품도 생산되지 않으면 그 종류의 수는 0이다.

입력

첫째 줄에 지시서 문자열 S가 주어진다.
1 ≤ S의 길이 ≤ 200,000
S는 A, B, 숫자 2부터 9, 여는 괄호 (, 닫는 괄호 )만으로 이루어진다.
S는 본문에서 정의한 올바른 지시서임이 보장된다.

출력

A형 부품 수와 B형 부품 수를 각각 1,000,000,007로 나눈 나머지를 공백으로 구분하여 출력한다.

A3(BA)B

4 4

2(A3(B))4(AA)

10 6

9(9(9(A)))

729 0

출처: Devin.KR 자체 제작