$\newcommand{ali}[1]{\begin{align*}#1\end{align*}}$$\ali{f_d(n)&=\sum\limits_{i=1}^n[(i,n)=1]i^d\\&=\sum\limits_{i=1}^ni^d\sum\limits_{\substack{k|i\\k|n}}\mu(k)\\&=\sum\limits_{k|n}\mu(k)k^d\sum\limits_{i=1}^{\frac nk}i^d}$

自然数幂求和是$d+1$次多项式，设$\sum\limits_{i=1}^ni^d=\sum\limits_{i=1}^{d+1}c_in^i$

$\ali{\sum\limits_{k|n}\mu(k)k^d\sum\limits_{i=1}^{\frac nk}i^d&=\sum\limits_{k|n}\mu(k)k^d\sum\limits_{i=1}^{d+1}c_i\left(\dfrac nk\right)^i\\&=\sum\limits_{i=1}^{d+1}c_i\sum\limits_{k|n}\mu(k)k^d\left(\dfrac nk\right)^i}$

令$H_i(n)=\sum\limits_{k|n}\mu(k)k^d\left(\frac nk\right)^i$，积性函数卷积性函数还是积性函数

所以答案为$\sum\limits_{i=1}^{d+1}c_i\prod\limits_{j=1}^{\omega}H_i\left(p_j^{\alpha_j}\right)$

其中$H_i(p,\alpha)=\sum\limits_{k=0}^\alpha\mu\left(p^k\right)p^{kd}p^{(\alpha-k)i}=p^{\alpha i}-p^{d+\alpha i-i}$

插出$c_i$后直接算即可，总时间复杂度$O(d^2+\omega d)$

#include
     
      #include
      
       typedef long long ll;const int mod=1000000007;int mul(int a,int b){return a*(ll)b%mod;}int ad(int a,int b){return(a+b)%mod;}int de(int a,int b){return(a-b)%mod;}int pow(int a,ll b){	int s=1;	while(b){		if(b&1)s=mul(s,a);		a=mul(a,a);		b>>=1;	}	return s;}namespace lar{	int x[110],y[110],f[110],g[110],h[110],n;	void work(){		int i,j,t;		g[0]=1;		for(i=0;i<=n;i++){			for(j=i;j>=0;j--)g[j+1]=g[j];			g[0]=0;			for(j=0;j<=i;j++)g[j]=de(g[j],mul(g[j+1],x[i]));		}		for(i=0;i<=n;i++){			memset(h,0,sizeof(h));			memcpy(h,g,sizeof(g));			t=1;			for(j=n;j>=0;j--){				if(i!=j)t=mul(t,de(x[i],x[j]));				h[j]=ad(h[j],mul(h[j+1],x[i]));			}			t=pow(t,mod-2);			for(j=0;j<=n;j++)f[j]=ad(f[j],mul(mul(y[i],t),h[j+1]));		}	}}int p[1010],a[1010],c[110],d;int H(int i,int p,int a){	return de(pow(p,(ll)a*i),pow(p,d+(ll)(a-1)*i));}int main(){	int n,i,j,s,t;	scanf("%d%d",&d,&n);	for(i=1;i<=n;i++)scanf("%d%d",p+i,a+i);	lar::n=d+1;	for(i=1;i<=d+1;i++){		lar::x[i]=i;		lar::y[i]=ad(lar::y[i-1],pow(i,d));	}	lar::work();	for(i=1;i<=d+1;i++)c[i]=lar::f[i];	s=0;	for(i=1;i<=d+1;i++){		t=1;		for(j=1;j<=n;j++)t=mul(t,H(i,p[j],a[j]));		s=ad(s,mul(c[i],t));	}	printf("%d",ad(s,mod));}