Задача CBS. Задано шаблон, що складається з круглих дужок та знаків питання.
Потрібно написати програму, яка визначить, скількома способами можна замінити знаки питання круглими дужками так, аби отримати правильну послідовність круглих дужок.
Правильна послідовність дужок (анлг. Correct Bracket Sequences) - окремий випадок послідовності з круглих дужок, що визначається таким чином:
ε (порожній рядок) є правильною послідовністю дужок;
нехай S - правильна послідовність, тоді (S) є правильна послідовність;
нехай S1, S2 - правильні послідовності, тоді S1S2 є правильна послідовність;
Приклади правильних послідовностей дужок ((()()()())), (())(()())
Технічні умови Програма Cbs читає з пристрою стандартного введення рядок довжиною не більше 10000 символів, виключно круглі дужки та знаки запитання. Програма виводить на пристрій стандартного виведення шукану величину – кількість способів по модулю 109+7.
Приклад
Введення
????(?
Виведення
2