Decompressed String Length

Interview

Time limit2sMemory limit128 MB

Summary

Compute the total length of a string after fully expanding nested K(Q) compression patterns, where K is a single digit repeat count.

Level: Medium4 of 10
Topics: Stack, String, Recursion
Solved: No attempts yet

Problem

A compressed string S is given. In the original uncompressed string, some substring may be written in the form K(Q). K is a one-digit integer, and Q is a string of length 0 or more. K(Q) means that the string Q is repeated K times. Given the compressed string S, compute the length of the string after it is fully decompressed.

Input

The first line contains the compressed string S. The length of S is at most 50. S consists only of (, ), and digits from 0 to 9.

Output

Print the length of the fully decompressed string on the first line. This value is at most 2,147,473,647.

Examples6

Example 1
Input
```
33(562(71(9)))
```
Expected output
```
19
```
Example 2
Input
```
123
```
Expected output
```
3
```
Example 3
Input
```
10342(76)
```
Expected output
```
8
```
Example 4
Input
```
0(0)
```
Expected output
```
0
```
Example 5
Input
```
1(1(1(1(1(1(1(0(1234567890))))))))
```
Expected output
```
0
```
Example 6
Input
```
1()66(5)
```
Expected output
```
7
```