ENG  RUSTimus Online Judge
Online Judge
О системе
Часто задаваемые вопросы
Новости сайта
Архив задач
Отправить на проверку
Состояние проверки
Исправить данные
Рейтинг авторов
Текущее соревнование
Прошедшие соревнования

SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Arrays Printing

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
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.

Исходные данные

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 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 } };
Источник задачи: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1618. Arrays Printing