D. Антон и школа - 2
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как вы уже, наверное, знаете, Антон учится в школе. Один из школьных предметов, который изучает Антон — скобкология. На уроках скобкологии школьники обычно изучают всякие последовательности, состоящие только из круглых скобок (символов «(» и «)» (без кавычек)).

На прошлом уроке Антон изучал правильные простые скобочные последовательности (ППСП). Скобочная последовательность 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.