第一题

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static Map<String, Integer> map = new HashMap<>();

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            String s = sc.next();

            System.out.println(removeCount(s));

        }
        sc.close();
    }

    public static int removeCount(String s) {

        if (s == null || s.isEmpty()) {
            return 1;
        }

        if (map.containsKey(s)) {
            return map.get(s);
        }

        int count = 0;

        String t = s.substring(1);

        for (int j = 0; j < t.length(); j++) {
            if (t.charAt(j) != ')') {
                continue;
            }

            String temp = t.substring(0, j) + t.substring(j + 1);
            if (isValid(temp)) {
                count += removeCount(temp);
            }
        }

        map.put(s, count);
        return count;
    }

    static boolean isValid(String s) {
        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                count++;
            }
            if (c == ')' && count-- == 0) {
                return false;
            }
        }

        return count == 0;
    }

}