Problem Description

Alice is playing a game with Bob.
Alice shows N integers a₁, a₂, …, a_N, and M, K. She says each integers 1 ≤ a_i ≤ M.
And now Alice wants to ask for each d = 1 to M, how many different sequences b₁, b₂, …, b_N. which satisfies :
1. For each i = 1…N, 1 ≤ b[i] ≤ M
2. gcd(b₁, b₂, …, b_N) = d
3. There will be exactly K position i that ai != bi (1 ≤ i ≤ n)

Alice thinks that the answer will be too large. In order not to annoy Bob, she only wants to know the answer modulo 1000000007.Bob can not solve the problem. Now he asks you for HELP!
Notes: gcd(x₁, x₂, …, x_n) is the greatest common divisor of x₁, x₂, …, x_n

 

Input

The input contains several test cases, terminated by EOF.
The first line of each test contains three integers N, M, K. (1 ≤ N, M ≤ 300000, 1 ≤ K ≤ N)
The second line contains N integers: a₁, a₂, ..., a_n (1 ≤ a_i ≤ M) which is original sequence.

 

Output

For each test contains 1 lines :
The line contains M integer, the i-th integer is the answer shows above when d is the i-th number.

 

Sample Input

 

Sample Output

 

Source

 

Recommend

zhuyuanchen520

 

 /* **********************************************

 Author      : kuangbin

 Created Time: 2013/8/13 16:39:35

 File Name   : F:\2013ACM练习\2013多校7\1010.cpp

 *********************************************** */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 using namespace std;

 const int MOD = 1e9+;

 long long pow_m(long long a,long long n)

 {

     long long ret = ;

     long long tmp = a%MOD;

     while(n)

     {

         if(n&)

         {

             ret *= tmp;

             ret %= MOD;

         }

         tmp *= tmp;

         tmp %= MOD;

         n >>= ;

     }

     return ret;

 }

 long long C[];

 //求ax = 1( mod m) 的x值，就是逆元(0<a<m)

 long long inv(long long a,long long m)

 {

     if(a == )return ;

     return inv(m%a,m)*(m-m/a)%m;

 }

 long long ans[];

 int a[];

 int num[];

 int b[];

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int N,M,K;

     while(scanf("%d%d%d",&N,&M,&K) == )

     {

         memset(num,,sizeof(num));

         for(int i = ;i <= N;i++)

         {

             scanf("%d",&a[i]);

             num[a[i]]++;

         }

         C[N-K] = ;

         for(int i = N-K+;i <= N;i++)

         {

             C[i] = C[i-]*i%MOD*inv(i-(N-K),MOD)%MOD;

         }

         for(int i = M;i>= ;i--)

         {

             int cnt = ;

             long long ss = ;

             for(int j = ; j*i <= M;j++)

             {

                 cnt += num[i*j];

                 if(j > )ss = (ss + ans[i*j])%MOD;

             }

             int t = M/i;

             if(t == )

             {

                 if(cnt == N-K)ans[i] = ;

                 else ans[i] = ;

                 continue;

             }

             if(cnt < N-K)

             {

                 ans[i] = ;

                 continue;

             }

             long long tmp = ;

             //在cnt个中选N-K个为相同的

             tmp =(tmp*C[cnt])%MOD;

             //其余的cnt-(N-K)个有t-1个选择

             tmp = ( tmp * pow_m(t-,cnt-(N-K)) )%MOD;

             //其余N-cnt个本来就不相同的，有t个选择

             tmp = (tmp * pow_m(t,N-cnt));

             ans[i] = (tmp - ss + MOD)%MOD;

         }

         for(int i = ;i <= M;i++)

         {

             printf("%I64d",ans[i]);

             if(i < M)printf(" ");

             else printf("\n");

         }

     }

     return ;

 }