code :

#include <iostream>
#include <stack>
#include <string>
using namespace std;
const int N=1e6+7, mod=10007;
struct node{
	int type;//0:number  1:option
	int num;char op;
	int lc, rc;
}tree[N];
int tot=0, root=0;
string s;
int jc[N];
stack<int> nums;
stack<char> opt;
int f(int x, int y){
	if(tree[x].type==0)
		return 1;
	int ans;
	if(tree[x].op=='&'){
		if(y==0){
			ans=((f(tree[x].lc, 0)%mod)*(jc[tree[tree[x].rc].num]%mod))%mod+((f(tree[x].lc, 1)%mod)*(f(tree[x].rc, 0)%mod))%mod;
		}else{
			ans=((f(tree[x].lc, 1)%mod)*(f(tree[x].rc, 1)%mod))%mod;
		}
	}else{
		if(y==1){
			ans=((f(tree[x].lc, 1)%mod)*(jc[tree[tree[x].rc].num]%mod))%mod+((f(tree[x].lc, 0)%mod)*(f(tree[x].rc, 1)%mod))%mod;
		}else{
			ans=((f(tree[x].lc, 0)%mod)*(f(tree[x].rc, 0)%mod))%mod;
		}
	}
	// cout<<"f("<<x<<", "<<y<<")="<<ans<<endl;
	return ans;
}
int main(){
	int n;
	cin>>n;
	cin>>s;
	jc[0]=1;
	for(int i=1;i<=1000000;i++){
		jc[i]=((jc[i-1]%mod)*2)%mod;
	}
	for(int i=0;i<n;i++){
		if(s[i]=='*') s[i]='&';
		else if(s[i]=='+') s[i]='|';
	}
	for(int i=0;i<s.size();i++){
		// cout<<i<<": "<<!((i>0 && s[i-1]==')') || s[i]=='(')<<" "<<s[i]<<endl;
		if(!((i>0 && s[i-1]==')') || s[i]=='(')){
			s.insert(s.begin()+i, '_');i++;
		}
	}
	if(s[s.size()-1]!=')')
		s=s+"_";
	// cout<<s<<endl;
	for(int i=0;i<s.size();i++){
		if(s[i]=='_'){
			nums.push(++tot);
			tree[tot].type=0;
			tree[tot].num=1;
			tree[tot].op='_';
		}else if(s[i]=='('){
			opt.push(s[i]);
		}else if(s[i]=='&'){
			while(opt.size() && opt.top()=='&'){
				char tmp=opt.top();opt.pop();
				tree[++tot].type=1;
				tree[tot].op=tmp;
				tree[tot].rc=nums.top();nums.pop();
				tree[tot].lc=nums.top();nums.pop();
				tree[tot].num=tree[tree[tot].lc].num+tree[tree[tot].rc].num;
				nums.push(tot);
			}
			opt.push(s[i]);
		}else if(s[i]=='|'){
			while(opt.size() && (opt.top()=='&' || opt.top()=='|')){
				char tmp=opt.top();opt.pop();
				tree[++tot].type=1;
				tree[tot].op=tmp;
				tree[tot].rc=nums.top();nums.pop();
				tree[tot].lc=nums.top();nums.pop();
				tree[tot].num=tree[tree[tot].lc].num+tree[tree[tot].rc].num;
				nums.push(tot);
			}
			opt.push(s[i]);
		}else{
			while(opt.size() && opt.top()!='('){
				char tmp=opt.top();opt.pop();
				tree[++tot].type=1;
				tree[tot].op=tmp;
				tree[tot].rc=nums.top();nums.pop();
				tree[tot].lc=nums.top();nums.pop();
				tree[tot].num=tree[tree[tot].lc].num+tree[tree[tot].rc].num;
				nums.push(tot);
			}
			opt.pop();
		}
	}
	while(opt.size()){
		char tmp=opt.top();opt.pop();
		tree[++tot].type=1;
		tree[tot].op=tmp;
		tree[tot].rc=nums.top();nums.pop();
		tree[tot].lc=nums.top();nums.pop();
		tree[tot].num=tree[tree[tot].lc].num+tree[tree[tot].rc].num;
		nums.push(tot);
	}
	root=nums.top();
	// for(int i=1;i<=tot;i++){
	// 	cout<<i<<" "<<tree[i].num<<" "<<tree[i].op<<" "<<tree[i].lc<<" "<<tree[i].rc<<endl;
	// }
	cout<<f(root, 0)<<endl;
    return 0;
}

#2 #6 #8 TLE

#9 WA