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

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

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; a₁, …, a_n are positive integers, a₁ · a₂ · … · a_n ≤ 512.

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

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

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 } };