main(f,n,s){for(;~scanf("%d%s",&f,s);vprintf("%d\n"))for(n=f;n-=strlen(s),n>0;)f*=n;}