d[3000][40];x,n,i,j,k,t,m=1e9+7;long p(a,n){return n?a*p(a,n-1)%m:1;}f(s,t,y,j){for(y=0;!(j=d[++y][0])?d[y--][0]=s:j-s?:!++d[y][t];);}main(s){for(scanf("%*d%d",&n);~scanf("%d",&s);s>1&&f(s,1))for(k=2;s%k<1?s/=k,++t:(t=t&&f(k,t),s>=k*k++););for(s=1;x=d[++i][0]?:!printf("%d",s);s=s*p(x,k)%m)for(k=t=0,j=30;t<n&&d[i][j]--?t++,k+=j:--j;);}