Динамическое программирование. Нахождения номера ПСП

Условие задачи: На детском утреннике одна правильная скобочная последовательность вела себя неправильно, и поэтому ее решили исключить из детского сада. Для протокола вам необходимо узнать ее номер в лексикографическом порядке. Формат ввода Единственная строка — данная правильная скобочная последовательность. Гарантируется, что ее длина не превышает 2*10^3. Формат вывода Выведите единственное целое число — номер данной последовательности в лексикографическом порядке среди всех правильных скобочных последовательностей той же длины. Поскольку это число может быть слишком большим, выведите его по модулю 10^9+7.

Вот мой код на c++:

   string s;
getline(cin,s);

int n=s.length();

s.insert(0,"#");//чтобы индексация строки начиналась с 1

vector<vector<ll>> dp(n+1,vector<ll>(n+1));//число ПСП длины b+l, т.ч первые b символов - открывающие скобки

dp[0][0]=1;

for (int l=1;l<=n;++l)
for (int b=0;b<=n;++b)
    dp[b][l]=(b<n?dp[b+1][l-1]:0)+(b>0?dp[b-1][l-1]:0);

ll ans=1;//номер ПСП - это 1 + сумма динамик начиная с i=1 до n dp[баланс (s1,...si)+2][n-i]

int b=0;//баланс строки s

for (int i=1;i<=n;++i){
    if(s[i]=='(')
        ++b;
    else{
        --b;
        ans+=dp[b+2][n-i];//нахождение суммы динамик
    }
}

cout<<ans%1e9+7<<'\n';

return 0;

} На примерах программа работает правильно, проходит несколько тестов, а дальше выдает неправильный результат. Пожалуйста, помогите разобраться.