Mathematics and Brackets
Once upon a time, three mathematicians gathered...
The first mathematician wrote a sequence of brackets on the board.
The second mathematician wondered if there was a cyclic shift that could turn this sequence into a valid one.
After some contemplation, the third mathematician announced the number of such shifts.
You are provided with the bracket sequence written by the first mathematician. Determine the number that the third mathematician declared.
A cyclic shift of a string involves moving a certain (possibly zero) number of characters from the end of the string to its beginning, while maintaining their order.
Input
The bracket sequence provided by the first mathematician is presented on a single line. The sequence's length is greater than zero and does not exceed 100000 characters.
Output
Output the number of cyclic shifts that convert the given bracket sequence into a valid one.