p=129402307,n,m,f,s,i;main(t){for(;read(0,&i,1);m=i-10?s+=f,(m*10+i-48)%(p-f):!f++?n=m,0:m);for(i=27;i--;)t=1L*t*t%p*(m>>i&1?n:1)%p;i=!printf("%d",n?t:s==!m);}