BracketSequenceDiv2

import java.util.*;

public class BracketSequenceDiv2 {
  static final int N = 100;
  static final int mod = 1_000_000_007;

  int add(int x, int y) {
    x += y;
    if (x >= mod)
      x -= mod;
    return x;
  }

  int sub(int x, int y) {
    x -= y;
    if (x < 0)
      x += mod;
    return x;
  }

  boolean order(int l, int m, int r) {
    return l <= m && m <= r;
  }

  public String checkData(String s) {
    int n = s.length();
    if (!order(1, n, N))
      return "s must contain between 1 and 100 characters, inclusive.";

    for (int i = 0; i < n; ++i) {
      char c = s.charAt(i);
      if (c != '(' && c != ')')
        return "Each character in s must be '(' or ')'.";
    }

    return "";
  }

  int naive(String s) {
    int n = s.length();
    Set<String> good = new HashSet<String>();

    for (int mask = 1; mask < (1 << n); ++mask) {
      int bal = 0;
      boolean bad = false;
      String cur = "";

      for (int i = 0; i < n; ++i)
        if (((mask >> i) & 1) == 1) {
          bal += s.charAt(i) == '(' ? 1 : -1;
          cur = cur + s.charAt(i);
        if (bal < 0)
         bad = true;
        }

      if (bal == 0 && !bad)
        good.add(cur);
    }

    return good.size();
  }


  public int count(String s) {
    int n = s.length();
    int[][] d = new int[N][2];

    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) == '(') {
        for (int j = N - 1; j >= 1; --j) {
          d[j][0] = add(d[j - 1][0], d[j - 1][1]);
          if (j == 1)
            d[j][0] = add(d[j][0], 1); //empty string counts
        }
      } else {
        for (int j = 0; j + 1 < N; ++j)
          d[j][1] = add(d[j + 1][0], d[j + 1][1]);
      }

      /*
      for (int j = 0; j < 5; ++j) {
        System.out.print(d[j][0]);
        System.out.print(" ");
        System.out.println(d[j][1]);
      }
      System.out.println();
      */
    }

    return d[0][1];
  }

  public static void main(String[] args) {
    BracketSequenceDiv2 solver = new BracketSequenceDiv2();
    String s = "(((((()))))()))";
    System.out.println(solver.count(s));
    System.out.println(solver.naive(s));
  }
};