program 

Nafets is working on an algorithm. Unfortunately, being very enthusiastic about the problem he's solving, he sometimes forgets to close the brackets which create the pseudo-code block structure. Therefore his algorithm can look like this: 
 (() 

 In this case, Nafets forgot to close a bracket. Depending on when he skipped said bracket the algorithm could have been (()) or ()().

Task 

Write a program that reads a sequence of round brackets representing Nafets' algorithm. Your program will have to calculate the number of algorithms (correctly closed sequences of brackets) Nafets may have thought of, knowing that he makes no other mistake except sometimes forget closing the brackets. 

Input Data 

Input file program.in contains on the first line the sequence of brackets corresponding to Nafets' algorithm.

Output Data 

If X is the number of possible algorithms, display on the first line of output file program.out the remainder after dividing X to 9731.

Restrictions 

• 1 <= number of brackets (open + closed) from the input file <= 400
• The sequence of brackets in the input file is obtained exactly in the way described in the problem's description 

Example 

Time limit: 0.1 seconds/test

Stefan Ciobaca
Universitat Konstanz
stefan.ciobaca@gmail.com