题解：
（吐槽：网上题解那个不严谨猜测真是没谁了……关键是还猜得辣么准……）
直接化简到求和那一段：
$f_{d}(n)=\sum_{t|n}\mu(t)t^{d}\sum_{i=1}^{\frac{n}{t}}i^{d}$
$设S_{d}(T)=\sum_{i=1}^{T}i^{d}$
那这个是什么呢？伯努利数（我会说我百度找到的吗……）
$s_{p}(T)=\sum_{i=1}^{p+1}\frac{(-1)^{p+1-i}C_{p+1}^{i}B_{p+1-i}}{p+1}n^{i}$(这个是百度那个公式化过来的)
然后$n^{i}$前面那一堆玩意就是网上题解的$a_{i}$。
接下来的化简我就不解释了……http://www.cnblogs.com/jianglangcaijin/p/4033399.html
然后我们只要求出C和B这题就没了。（貌似可以把d的范围再扩10倍233）
代码：
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=1e9+;
const int N=;
inline ll read(){
ll s=,k=;char ch=getchar();
while(ch<''|ch>'') ch=='-'?k=-:,ch=getchar();
while(ch>&ch<='') s=s*+(ch^),ch=getchar();
return s*k;
}
inline ll powmod(ll a,ll b){
ll ans=;
if(b<)
return powmod(powmod(a,mod-),-b);
a%=mod;
while(b){
if(b&) ans=ans*a%mod;
b>>=;a=a*a%mod;
}return ans;
}
ll w,d;
ll p[N],pk[N];
ll tot=;
inline ll calc(int n){
ll t=powmod(tot,n);
for(int i=;i<=w;i++){
t=t*(1ll-powmod(p[i],d-n))%mod;
}
if(t<) t+=mod;
return t;
}
ll c[][],b[];
int main(){
d=read(),w=read();
ll n=w;
for(int i=;i<=n;i++){
p[i]=read(),pk[i]=read();
tot=tot*powmod(p[i],pk[i])%mod;
}
c[][]=;
for(int i=;i<=;i++){
c[i][]=;
for(int j=;j<=i;j++)
c[i][j]=(c[i-][j]+c[i-][j-])%mod;
}
b[]=;
for(int i=;i<=;i++){
for(int j=;j<i;j++)
b[i]=(b[i]+c[i+][j]*b[j])%mod;
b[i]=b[i]*(-powmod(i+,mod-))%mod+mod;
b[i]%=mod;
}
ll ans=;
ll inv=powmod(d+,mod-);
for(int i=;i<=d+;i++){
ll temp=((d+-i&)?-:)*c[d+][i]*b[d+-i]%mod*inv%mod;
if(temp==)
continue;
temp=temp*calc(i)%mod;
ans+=temp;
ans%=mod;
}
printf("%lld\n",(ans%mod+mod)%mod);
}
/*
3 2
2 1
5 1
*/