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