Description：

$$ \prod_{i_1=1}^n\prod_{i_2=1}^n …\prod_{i_k=1}^n \varphi\big(lcm(i_1,i_2,…,i_k)\big) $$

$1\leqslant n\leqslant 10^6$

Solution：

首先由于 $\varphi$ 是积性函数可以把每个质因子分别考虑，也就是说： $$ \begin{align} ans&=\prod_{i=1}^k\prod_{i_1=1}^n\prod_{i_2=1}^n\cdots\prod_{i_k=1}^n\prod_x[\max(q_{i_1},q_{i_2},\dots)=x]\varphi\big(p_i^x\big)\\ &=\prod_{i=1}^k\prod_x\varphi(p_i^x)^{\sum_{i_1=1}^n\sum_{i_2=1}^n\cdots\sum_{i_k=1}^n[\max(q_{i_1},q_{i_2},\dots)=x]} \end{align} $$ 设 $cnt[x]=\sum_{i_1=1}^n\sum_{i_2=1}^n\cdots\sum_{i_k=1}^n[\max(q_{i_1},q_{i_2},\dots)=x]$ ，但是这个不好直接计算，我们考虑： $$ cnt'[x]=\sum_{i_1=1}^n\sum_{i_2=1}^n\cdots\sum_{i_k=1}^n[\max(q_{i_1},q_{i_2},\dots)\geqslant x]=n^k-(n-\lfloor\frac n {p_i^x}\rfloor)^k $$ 那 $cnt[x]=cnt'[x]-cnt'[x+1]$ ，然后就可以直接求了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 1000010

#define MOD 1000000007

#define PHI 1000000006

bool isprime[MAXN];

int prime[MAXN],tot = 0;

int phi[MAXN];

void sieve()

{

	for(int i = 2;i <= n;++i)isprime[i] = true;

	phi[1] = 1;

	for(int i = 2;i <= n;++i)

	{

		if(isprime[i])prime[++tot] = i,phi[i] = i - 1;

		for(int j = 1;j <= tot && i * prime[j] <= n;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)

			{

				phi[i * prime[j]] = phi[i] * prime[j];

				break;

			}

			else phi[i * prime[j]] = phi[i] * phi[prime[j]];

		}

	}

	return;

}

int power(int a,int b,int p)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % p;

		a = 1ll * a * a % p;

		b = b >> 1;

	}

	return res;

}

int calc(int n,long long p)

{

	return (power(n,k,PHI) - power(n - (n / p),k,PHI) + PHI) % PHI;

}

int main()

{

	scanf("%d%d",&n,&k);

	sieve();

	int ans = 1;

	for(int i = 1;i <= tot;++i)

	{

		long long p = 1;

		for(int x = 0;p <= n;++x,p = p * prime[i])

		{

			int cnt = (calc(n,p) - calc(n,p * prime[i]) + PHI) % PHI;

			ans = 1ll * ans * power(phi[p],cnt,MOD) % MOD;

		}

	}

	cout << ans << endl;

	return 0;

}