#include <bits/stdc++.h>
using namespace std;

// [1] m-取模的模数，题目要求得分 mod 12345678910，避免得分过大溢出
long long m=12345678910;

int main() {
    // [2] n-括号字符串的长度（输入的正整数，2≤n≤1e5）
	int n;
	cin >> n ;
    // [3] s-输入的合法括号字符串（仅包含'('和')'，题目保证合法嵌套）
	string s;
	cin>>s;
    // [4] v-栈，用于维护括号嵌套的得分：栈中每个元素代表当前嵌套层级的累计得分，初始压入0作为根层级的初始得分
	stack<long long> v;
	v.push(0);

    // [5] 遍历括号字符串的每个字符，计算防御能力得分
	for(int i=0;i<n;i++){
        // [6] 情况1：遇到左括号'('，表示进入新的嵌套层级，压入0作为该层级的初始得分
		if(s[i]=='('){
			v.push(0);
        // [7] 情况2：遇到右括号')'，表示当前嵌套层级结束，计算该层级的得分
		}else{
            // [8] score-当前层级的防御得分
			long long score=0;
            // [9] 判断当前层级是否为最内层括号（栈顶为0表示该括号内无其他括号）
			if(v.top()==0){
				score=1;  // 最内层括号得分1（规则1）
			}else{
				score=v.top()*2%m;  // 嵌套括号得分=内层得分×2（规则2），取模避免溢出
			}
            // [10] 弹出当前层级的得分（因为该层级已处理完毕）
			v.pop();
            // [11] 将当前层级的得分累加到上一层级的得分中（规则3：并列括号得分相加），再取模
			v.top()=(score+v.top())%m; 
		}
	}
    // [12] 栈顶存储的是整个括号字符串的总防御得分，输出结果
	cout<<v.top();
	return 0;
}