/* Topcoder SRM 714, D2, 500-pointer.
   RemovingParenthesis
   James S. Plank
   Mon May 15 15:56:16 EDT 2017
 */

#include <string>
#include <map>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class RemovingParenthesis
{
    public:
        int countWays(string s);
        map <string, int> C;
};

int RemovingParenthesis::countWays(string s)
{
    int i, j;
    int legal;     // Is the new string legal?
    int level;     // Use this to keep track of nesting level when testing for legality.
    int total;     // Sum of all recursive calls.
    string s2;     // The string that we build from deleting characters 0 and i.

    /* Base case -- return 1 for the empty string. */

    if (s.size() == 0) return 1;

    /* Check the cache to see if you've solved this one already. */

    if (C.find(s) != C.end()) return C[s];

    total = 0;

    /* Run through each character starting with i=1.
       If the character is a right paren, then construct
       s2 by deleting characters 0 and i.  Use substr()
       to do this. */

    for (i = 1; i < s.size(); i++) {

        if (s[i] == ')') {
            s2 = (s.substr(1, i-1) + s.substr(i+1));

            /* Now test s2 for legality */

            legal = 1;
            level = 0;

            for (j = 0; j < s2.size(); j++) {

                if (s2[j] == '(') {
                    level++;
                } else {
                    level--;
                }

                if (level < 0) legal = 0;
            }

            /* The constraints guarantee that level will = 0
               at the end of the loop above.  If they didn't,
               I should make sure that level equals 0 here. */

            /* If it's legal, then make the recursive call. */

            if (legal) total += countWays(s2);
        }
    }

    /* Memoize and return at the end. */

    C[s] = total;
    return total;
}