| Codeforces Round 404 (Div. 2) |
|---|
| Закончено |
Как вы уже, наверное, знаете, Антон учится в школе. Один из школьных предметов, который изучает Антон — скобкология. На уроках скобкологии школьники обычно изучают всякие последовательности, состоящие только из круглых скобок (символов «(» и «)» (без кавычек)).
На прошлом уроке Антон изучал правильные простые скобочные последовательности (ППСП). Скобочная последовательность s длины n является ППСП, если соблюдаются следующие условия:
- Она не является пустой (то есть n ≠ 0).
- Длина последовательности четна.
- Первые
символов последовательности равны «(». - Последние символов последовательности равны «)».
Например, последовательность «((()))» является ППСП, а вот последовательности «((())» и «(()())» — нет.
На дом учитель Антона, Елена Ивановна, задала Антону такую задачу. Дана некоторая скобочная последовательность s. Необходимо найти количество ее различных подпоследовательностей таких, что они являются ППСП. Напомним, что подпоследовательностью строки s называется такая строка, которая была получена вычеркиванием из s некоторых символов. Две подпоследовательности считаются различными, если множества позиций вычеркнутых символов различаются.
Так как ответ может быть очень большим, а учителю Антона не нравятся большие числа, то она просит Антона найти ответ по модулю 109 + 7.
Антон долго думал над этой задачей, однако так и не придумал, как ее решить. Помогите Антону решить эту задачу и напишите программу, которая находит ответ на нее!
В единственной строке входных данных находится строка s — исходная скобочная последовательность. Эта строка состоит только из символов «(» и «)» (без кавычек). Гарантируется, что строка непуста и ее длина не превосходит 200 000.
Выведите одно целое число — ответ на задачу по модулю 109 + 7.
)(()()
6
()()()
7
)))
0
В первом примере возможны следующие подпоследовательности:
- Если вычеркнуть символы на позициях 1 и 5 (нумерация начинается с единицы), то получим подпоследовательность «(())».
- Если вычеркнуть символы на позициях 1, 2, 3 и 4, то получим подпоследовательность «()».
- Если вычеркнуть символы на позициях 1, 2, 4 и 5, то получим подпоследовательность «()».
- Если вычеркнуть символы на позициях 1, 2, 5 и 6, то получим подпоследовательность «()».
- Если вычеркнуть символы на позициях 1, 3, 4 и 5, то получим подпоследовательность «()».
- Если вычеркнуть символы на позициях 1, 3, 5 и 6, то получим подпоследовательность «()».
Остальные подпоследовательности не являются ППСП. Итого получили 6 различных подпоследовательностей, которые являются ППСП, поэтому ответ — 6.
