public void solve() throws IOException {
    int n = nextInt();
    int m = nextInt();
    String s = nextLine();
    int pre = 0, post = 0;
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '(') {
        post++;
      } else if (post != 0) {
        post--;
      } else {
        pre++;
      }
    }
    post = Math.max(0, post);
    int diff = n - m;
    int remain = diff - post - pre;
    System.out.println(remain + " " + post + " " + pre);
    if (pre + post > diff || remain % 2 != 0) {
      out.println(0);
    } else if (remain == 0) {
      out.println(1);
    } else {
      long total = 0;
      for (int i = 0; i <= remain; i++) {
        int leftlength = pre + i;
        int rightlength = post + remain - i;
        long leftcount = (choose(leftlength, i) 
            - choose(leftlength, i + 1) + MOD) % MOD;
        long rightcount = (choose(rightlength, remain - i) 
            - choose(rightlength, remain - i + 1) + MOD) % MOD;
        System.out.println(i + " " + leftcount + " " + rightcount);
        total += (leftcount * rightcount) % MOD;
        total %= MOD;
      }
      out.println(total);
    }
  }