Задача Bracket. В складних математичних виразах доводиться інколи ставити багато дужок. Часто буває важко порахувати, скільки дужок відкрито і скільки закрито. Аби спростити запис, крім круглих дужок “(“ і “)”, застосовується права квадратна дужка “]”. , яка закриває усі відкриті на даний момент дужки, якщо такі є (якщо відкритих дужок до правої квадратної немає, вираз є помилковим). Правильним «дужковим» виразом будемо називати рядок символів, отриманий з правильного виразу після викреслювання з нього усіх символів, крім дужок “(“, “)” и “]”.
Наприклад, правильними «дужковим» виразом є (()(()(()](), ((((((], (())(). А ось приклади неправильних «дужкових» виразів:())((((] – помилка у третьому символі, (())] – квадратній дужці нічого закривати,((])) – дужка, що йде за квадратною, не має відкритої пари.Порожній рядок є правильним «дужковим» виразом. Напишіть програму, яка для даного рядка, що містить лише символи “(“, “)” и “]”, визначить, скільки є способів викреслити якусь кількість (можливо 0) символів так, аби ті, що залишились, утворили правильний «дужковий» вираз.
Технічні умови. Програма Bracketчитає з клавіатури рядок із символів "(“, “)” або “]”. Кількість дужок у рядку – від 1 до 768. Програма виводить на екран єдине число – шукану величину по модулю 1 000 007
Приклади
|
Введення |
Виведення |
|
()() |
5 |
|
Введення |
Виведення |
|
)])] |
1 |
|
Введення |
Виведення |
|
(())] |
11 |