Codeforces Famil Door and Brackets Solution

import java.io.BufferedReader;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Famildoorandbracket {

 public static void main(String[] args) throws IOException
 {
  MyScannerfdb sc=new MyScannerfdb();
  int n=sc.nextInt();
  int m=sc.nextInt();
  String s=sc.nextLine();
  //File t=new File("testwrite.txt");
  //FileWriter file=new FileWriter(t);
  //PrintWriter pw=new PrintWriter(file,true);
  
  int i,j;
  long MOD=(long) (1e9+7);
  
  
  int balance=0;
  int minvalue=Integer.MAX_VALUE;
  for(i=0;i<m;i++)
  {
   if(s.charAt(i)=='(')
    balance++;
   else
    balance--;
   minvalue=Math.min(minvalue,balance);
  }
  long dp[][] = new long[n-m+1][n-m+1];
  for(i = 0; i <= n-m; i++) {
   if(i == 0) {
    dp[0][0] = 1;
    continue;
   }
   else {
    dp[i][0] = dp[i - 1][1];
   }
   
   for( j = 1; j <= i; j++) {
    
    dp[i][j] += dp[i - 1][j - 1];
    if(j<n-m)
    dp[i][j]+=dp[i - 1][j + 1];
    dp[i][j]=(dp[i][j]% MOD);
    
   }
   
  }
  //for(long a[]:dp)
  //{
   //pw.println(Arrays.toString(a));
  //}
  
  long result=0;
  for(i=0;i<=n-m;i++)
  {
   for(j=0;j<=i;j++)
   {
    if((j+balance)>n-m-i)
     continue;
    if((j+minvalue)<0)
     continue;
    result=(result+(dp[i][j]*dp[n-m-i][j+balance])%MOD)%MOD;
    
   }
  }
  System.out.println(result);

 }

}
class MyScannerfdb
{
 BufferedReader br;
 StringTokenizer st;
 MyScannerfdb()
 {
  br=new BufferedReader(new InputStreamReader(System.in));
 }
 String next()
 {
  
  while(st==null || !st.hasMoreTokens())
  {
   try
   {
    st=new StringTokenizer(br.readLine());
   }
   catch(Exception e)
   {
    e.printStackTrace();
   }
  }
  return st.nextToken();
  
 }
 int nextInt()
 {
  return Integer.parseInt(next());
 }
 long nextLong()
 {
  return Long.parseLong(next());
 }
 double nextDouble()
 {
  return Double.parseDouble(next());
 }
 String nextLine()
 {
  String str="";
  try
  {
   str=br.readLine();
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }
  return str;
  
 }
}