背景

zhx和他的妹子出去玩。

描述

请在此填写题目描述

输入格式

仅一行，包含两个数N和M.

输出格式

仅一行，包含所求的答案mod 10^9 + 7的值。

【样例输入】

3 3

【样例输出】

备注

对于 50%的数据，所有1≤N,M≤1000。

对于100% 的数据，所有1≤N,M≤50000 。

题解：

等比数列：{a,aq₁,aq₂,aq₃,aq₄,aq₅...aq_n,...}

前m项的前缀和：s=a(1-q^m)/(1-m);

费马小定理：若p为质数，a^p-1%p=1

逆元：若ax%p=1(p为质数)，则a,x互为逆元

则ans=sigma（1,n）q(1-q^m)/(1-m)

由于同余定理不支持除法，逆元处理:

ans=sigma（1,n）q(1-q^m)/(1-q)^mod-2

考虑到负数问题

ans=sigma（1,n）q(q^m-1)/(q-1)^mod-2

最终

ans=sigma（1,n）q(q^m-1)/(q-1)^mod-2

代码：

#include
     
      #include
      
       #define ll long longusing namespace std;const ll mod=1e9+7;ll n,m;inline ll fpow(ll a,ll p){    ll res=1;    for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod;    return res%mod;}inline void solve(){    ll ans=n;    for(ll i=2,tmp,s;i<=n;i++){        /*自己推的*/         //tmp=fpow(i,m+1);        //s=((tmp-1+mod)%mod)*fpow(i-1,mod-2)%mod;        //ans=(ans+s-1+mod)%mod;        /*学哥讲的等比数列*/         tmp=i*(fpow(i,m)-1)%mod;        s=fpow((i-1),mod-2);        ans=(ans+tmp*s%mod)%mod;    }//应该是都对     cout<
       
        >n>>m;    solve();    return 0;}