Append — 부호열 분할 개수

잘 알려진 압축 알고리즘에서 쓰이는 부호화 방식을 생각하자. 소문자 알파벳으로만 이루어진 문자열을 부호화한다. 이러한 문자열은 쌍 $(p_i, r_i)$ 들의 나열로 부호화되며, $p_i \ge 0$ 은 정수이고 $r_i$ 는 $p_i = 0$ 일 때는 하나의 문자, $p_i > 0$ 일 때는 $0 < r_i \le p_i$ 를 만족하는 정수이다.

복호화는 쌍을 순서대로 처리하면서 결과 문자열을 만들어 간다.

• $p_i = 0$ 이면 $r_i$ 는 문자이며, 지금까지 복호화된 문자열의 끝에 그 문자를 덧붙인다.
• $p_i > 0$ 이면 $r_i$ 는 $0 < r_i \le p_i$ 인 정수이며, 지금까지 복호화된 문자열의 현재 끝에서 $p_i$ 칸 앞의 위치부터 시작해 $r_i$ 개의 문자를 복사하여 끝에 덧붙인다.

예를 들어 쌍 $(0, a), (1, 1), (0, b), (3, 3), (3, 3), (3, 2), (0, c)$ 는 다음과 같이 복호화된다. $(0, a)$ 로 a, $(1, 1)$ 로 aa, $(0, b)$ 로 aab, $(3, 3)$ 은 aab 를 덧붙여 aabaab, 다음 $(3, 3)$ 은 다시 aab 를 덧붙여 aabaabaab, $(3, 2)$ 는 aa 를 덧붙여 aabaabaabaa, 마지막으로 $(0, c)$ 로 aabaabaabaac 가 된다. 하나의 문자열 $w$ 에 대해 서로 다른 부호가 여러 개 존재할 수 있음에 유의하라.

두 문자열 $u$, $v$ 에 대해 $uv$ 는 이들을 이어 붙인 문자열을 뜻한다. $C_w$ 를 소문자 문자열 $w$ 의 한 부호라고 하자. 주어진 부호 $C_w$ 를 앞뒤로 이어지는 두 부분 $C_w = C_u C_v$ 로 나누는 방법이 몇 가지인지 세어라. 단,

• $C_u$ 는 앞쪽 몇 개의 쌍으로 이루어진 접두부이고, $C_v$ 는 나머지 접미부이다.
• $C_u$ 자체가 어떤 문자열 $u$ 의 올바른 부호이고, $C_v$ 자체도 어떤 문자열 $v$ 의 올바른 부호이다.
• $w = uv$ 이며 $u$ 와 $v$ 는 모두 비어 있지 않다.

이 개수를 출력하는 프로그램을 작성하라.

입력은 여러 개의 블록으로 이루어진다. 각 블록은 하나의 부호 $C_w$ 를 나타낸다. 블록의 각 줄은 공백 하나로 구분된 두 정수 $p_i$, $r_i$ ($r_i \le p_i < 1000$) 이거나, 정수 $0$ 뒤에 공백 하나와 소문자 하나가 오는 형태이다. 각 블록은 빈 줄 하나로 끝난다. 입력에는 이러한 블록이 여러 개 연달아 주어질 수 있다.

각 블록마다 한 줄에, 부호 $C_w$ 를 $w = uv$ 이고 $u$, $v$ 가 모두 비어 있지 않으며 두 부분이 각각 그 자체로 올바른 부호가 되도록 $C_u C_v$ 로 나누는 방법의 수를 출력한다.