#define F(d,e)for(i=m*2;i--;)w[k]+=s[u[i]]-s[k=u[i^1]]-d?0:e w[u[i]];
ll i,m,r,k,u[2d5],w[2d5];char s[2d5];{rd(m,m,s+1,u(m*2));F(12,!)F(1,)F(2,r+=);wt(r%MD);}