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

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

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

Приклади

Введення

Виведення

()()

5

Введення

Виведення

)])]

1

Введення

Виведення

(())]

11

 

© LIKT 1998-2018