Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Bracket

Задача Bracket. В складних математичних виразах доводиться інколи ставити багато дужок. Часто буває важко порахувати, скільки дужок відкрито і скільки закрито. Аби спростити запис, крім круглих дужок “(“ і “)”, застосовується права квадратна дужка “]”. , яка закриває усі відкриті на даний момент дужки, якщо такі є (якщо відкритих дужок до правої квадратної немає, вираз є помилковим). Правильним «дужковим» виразом будемо називати рядок символів, отриманий з правильного виразу після викреслювання з нього усіх символів, крім дужок “(“, “)” и “]”.

Наприклад, правильними «дужковим» виразом є (()(()(()](), ((((((], (())(). А ось приклади неправильних «дужкових» виразів:())((((] – помилка у третьому символі, (())] – квадратній дужці нічого закривати,((])) – дужка, що йде за квадратною, не має відкритої пари.Порожній рядок є правильним «дужковим» виразом. Напишіть програму, яка для даного рядка, що містить лише символи “(“, “)” и “]”, визначить, скільки є способів викреслити якусь кількість (можливо 0) символів так, аби ті, що залишились, утворили правильний «дужковий» вираз.

Технічні умови. Програма Bracketчитає з клавіатури рядок із символів "(“, “)” або “]”. Кількість дужок у рядку – від 1 до 768. Програма виводить на екран єдине число – шукану величину по модулю 1 000 007

Приклади

Введення

Виведення

()()

5

Введення

Виведення

)])]

1

Введення

Виведення

(())]

11


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"