Встретились однажды три математика…
- Первый математик написал мелом на доске скобочную последовательность.
- Второму математику стало интересно, существует ли циклический сдвиг, превращающий эту последовательность в правильную.
- Третий же математик, немного подумав, сказал, сколько таких сдвигов существует.
Вам известна скобочная последовательность, записанная первым математиком. Найдите число, которое произнёс третий математик.
Напомним определение правильной скобочной последовательности:
- пустая строка является правильной скобочной последовательностью;
- если строка a — правильная скобочная последовательность, то строка (a) — тоже правильная скобочная последовательность;
- если строки a и b — правильные скобочные последовательности, то строка ab — тоже правильная скобочная последовательность.
- других правильных скобочных последовательностей нет.
Циклическим сдвигом строки называется перенос некоторого (возможно, нулевого) количества символов из конца строки в её начало без изменения их порядка.
Исходные данные
В единственной строке дана скобочная последовательность, записанная первым математиком.
Длина последовательности не равна нулю и не превышает 100000 символов.
Результат
Выведите количество циклических сдвигов, превращающих
записанную скобочную последовательность в правильную.
Примеры
| исходные данные | результат |
|---|
)(()
| 1 |
)()(
| 2 |
()
| 1 |
Автор задачи: Александр Торопов
Источник задачи: XIV Открытое командное первенство школьников Свердловской области по программированию
