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