e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Математики и скобки

Математики и скобки

Встретились однажды три математика...

  • Первый математик написал на доске скобочную последовательность.
  • Второму математику стало интересно, существует ли циклический сдвиг, превращающий эту последовательность в правильную.
  • Третий же математик, немного подумав, сказал, сколько таких сдвигов существует.

Вам известна скобочная последовательность, записанная первым математиком. Найдите число, которое произнёс третий математик.

Циклическим сдвигом строки называется перенос некоторого (возможно, нулевого) количества символов из конца строки в её начало без изменения их порядка.

Входные данные

В единственной строке дана скобочная последовательность, записанная первым математиком. Длина последовательности не равна нулю и не превышает 100000 символов.

Выходные данные

Выведите количество циклических сдвигов, превращающих записанную скобочную последовательность в правильную.

Time limit 1 second
Memory limit 64 MiB
Input example #1
)(()
Output example #1
1