#define F(d,e)for(i=m*2;i--;)s[u[i]]-s[u[i^1]]-d||(w[u[i^1]]+=e w[u[i]]);
ll i,m,r,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);}