题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3434

题意：

思路：

const int mod=10007;const int N=100005;   int g[22][N];int C[N][22],mou[N];int h[22][N][13];    int prime[N],cnt;int tag[N]; void init(){    int i,j;     mou[1]=1;    for(i=2;i
     
      =N) break;            tag[i*prime[j]]=1;            if(i%prime[j]==0)            {                mou[i*prime[j]]=0;                break;            }            else mou[i*prime[j]]=-mou[i];        }    }     C[0][0]=1;    for(i=1;i
      
       =mod) C[i][j]-=mod;        }    }    int c;    for(c=2;c<=20;c++)    {        for(i=1;i
       
        =mod) g[c][j]-=mod;            if(g[c][j]<0) g[c][j]+=mod;        }    }       for(c=2;c<=20;c++)    {        for(i=1;i
        
         =mod) x%=mod;            for(j=0;j<=11;j++)            {                h[c][i][j]=pre*g[c][i]%mod;                h[c][i][j]+=h[c][i-1][j];                if(h[c][i][j]>=mod) h[c][i][j]-=mod;                pre=pre*x%mod;            }        }    }}   int n,cc,M[13];         struct node{    int a[15];      int Max;     void clear()    {        clr(a,0);        Max=0;    }          void mul(int x1,int x0)    {        int i;        int b[15];        for(i=0;i<=Max;i++) b[i]=a[i]*x0%mod;        b[Max+1]=0;         for(i=0;i<=Max;i++)        {            b[i+1]=b[i+1]+a[i]*x1%mod;            if(b[i+1]>=mod) b[i+1]-=mod;        }         for(i=0;i<=n;i++) a[i]=b[i];        Max++;    }   }A;   int cal(int d1,int d2){    A.clear();    A.a[0]=1;    int i;    for(i=1;i<=n;i++)    {        i64 tmp=M[i]/d1;        int aa=-(i64)(tmp+1)*tmp/2%mod;        int bb=M[i]%mod*tmp%mod;        A.mul(aa,bb);    }    int ans=0;    for(i=n;i>=0;i--)    {        ans+=A.a[i]*(h[cc][d2][i]-h[cc][d1-1][i])%mod;        if(ans<0) ans+=mod;        if(ans>=mod) ans-=mod;    }    return ans;}   int main(){    init();       int T=getInt();       while(T--)    {        n=getInt();        cc=getInt();        int i;        for(i=1;i<=n;i++) M[i]=getInt();        sort(M+1,M+n+1);        int ans=0;              for(i=1;i<=M[1];)        {            int L=i;            int R=M[1];                  int j;            for(j=1;j<=n;j++)            {                R=min(R,M[j]/(M[j]/i));            }               ans+=cal(L,R);               if(ans>=mod) ans-=mod;            if(ans<0) ans+=mod;               i=R+1;        }        printf("%d\n",ans);    }}