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

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

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

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

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

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

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

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

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