ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1618. Arrays Printing

Time limit: 2.0 second
Memory limit: 64 MB
Java language contains arrays as special classes. Since every class in Java derives from java.lang.Object, every array does, too. An array of objects can contain other arrays as elements. In this problem, we consider only arrays that contain other arrays as elements, or arrays that are empty.
Sometimes we should print the given array as a string. To do this, we may use the dedicated method, java.util.Arrays.deepToString. This method returns a string representation of the "deep contents" of the specified array. If the array contains other arrays as elements, the string representation contains their contents and so on. This method is designed for converting multidimensional arrays to strings.
The string representation consists of a list of the array's elements, enclosed in square brackets ("[]"). Adjacent elements are separated by the characters ", " (a comma followed by a space). All the elements are converted to strings by invoking this method recursively.
For example, we may take the array
Object[] A = new Object[2];
A[0] = new Object[0];
A[1] = new Object[0];
and the invocation of deepToString on it will return [[], []].
Note that a variable of object type in Java is a reference. As a result, an array may contain the same object more than once, and two arrays may contain the same object as an element. So, different arrays may give the same string representation. For example, the array
Object[] B = new Object[2];
B[0] = new Object[0];
B[1] = B[0];
will have the same string representation as array A has.
Let's determine the equality relation for array configurations. Two configurations A and B are considered equal if the following statements
  • A[a1][a2]…[ak] == A[b1][b2]…[bk]
  • B[a1][a2]…[ak] == B[b1][b2]…[bk]
are equivalent for all possible sequences of ai and bj. Here, the relation "==" should be treated as "equal by reference".
Given the outcome of the invocation of deepToString, find the number of different array configurations that give the specified result. You may assume that the given string will be a string representation of multidimensional array with constant dimensions created with the construction new Object[a1][a2]…[an][0]. Here n ≤ 100; a1, …, an are positive integers, a1 · a2 · … · an ≤ 512.

Input

The input will consist of a single non-empty string S with length not exceeding 105. This string will be an outcome of calling deepToString on an array of the described type.

Output

Output the number of array configurations with the given string representation modulo 10007.

Samples

inputoutput
[[], []]
2
[[[[]]]]
1
[[[]], [[]]]
3

Notes

The arrays in the third example were created by the following statements:
  1. third = new Object[2][1][0];
    
  2. Object level1 = new Object[1][0];
    third = new Object[] { level1, level1 };
    
  3. Object level2 = new Object[0];
    third = new Object[] { new Object[] { level2 }, new Object[] { level2 } };
    
Problem Source: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.