Under construction

Still being built. Things may change

Universal Life Genome Database Returns

Time limit8sMemory limit512 MB

Summary
Given a genome string S with nested repeat counts and a pattern Q, count how many times Q occurs in the fully expanded S, overlaps included.
Level

Medium7 of 10

Topics
String matching, Dynamic programming, Recursion
Solved
No attempts yet

Problem

In the year 2301 AD, the Life Science Bureau of the Space Federation Republic was studying the genome sequences of space organisms. Recent research has shown that how many times a specific pattern appears in a genome sequence strongly affects the traits of the organism.

A space organism's genome sequence is a string of uppercase English letters. The researchers want to count how many times a given pattern appears in the genome sequence. Because these sequences are very long, the database stores them with repeated substrings compressed using the method below.

Your task is to write a program that counts how many times a string QQ appears in the compressed genome sequence SS. Occurrences of QQ are counted separately whenever their starting positions differ, even if they overlap. For example, ISSI appears 2 times in MISSISSIPPI.

The compression format is defined by the following BNF.

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

An integer placed before a string means that the string is repeated that many times. For example, 5A is AAAAA, and 2(AB) is ABAB. If an integer has no parentheses after it, only the single letter that follows is repeated. For example, 2AB is AAB. Repetitions can be nested to any depth. 2(2(AB)C) is the same as 2(ABABC), which expands to ABABCABABC.

Input

The input contains at most 50 datasets. Each dataset has the following format.

S
Q

The first line is the compressed genome sequence SS. SS follows the BNF above and has a length from 1 to 3000 characters. The fully expanded genome sequence of SS has a length of at most 101810^{18}. The second line is the string QQ to count. QQ consists of uppercase English letters and has a length from 1 to 3000 characters.

The input ends with a line that contains only the character '#'.

Output

For each dataset, print how many times QQ appears in the string obtained by expanding SS.

Examples1

  1. Example 1

    Input
    MI2(2SI)2PI
ISSI
100(100(JAG))
JAG
1000000000000000000A
AAAAA
#
    Expected output
    2
10000
999999999999999996