Alex love Number theory. Today he think a easy problem, Give you number N and L, To calculate N^1 + N^2 + N^3 + ... + N^L, And ans will mod 1e9+7

Many test of input(about 10W case), each input contains number N and L, 1 <= N, L <= 2147483647

Contains a number with your answer

#include<iostream>

#include<cstring>

#include<cstring>

#include<cstdio>

using namespace std;

const int MOD = ;  // 宏定义也行

typedef long long ll;  // __int64也行

ll pow_mod(ll x, ll k)   // 快速幂函数

{

    ll ans = ;

    if(k == )

        return x;

    while(k)

    {

        if(k&)

            ans = (ans * x) % MOD;

        x = (x * x) % MOD;

        k >>= ;     // k  /= 2

    }

    return ans;
 //     (n*n*n*n*n)%Mod = (( ((n*n)%Mod) *((n*n)%Mod) ) % Mod) * (n % Mod)  ,记住就行了~至于为什么，目前我还不知道

}

ll magic(ll n, ll l)

{

    if(l == )

        return n; 

    ll tmp = magic(n, l/);  // 递归，二分，先求l部分的前一半项

    ll ste = (tmp + (pow_mod(n, l/) * tmp )% MOD) % MOD;  // n+n*n+n*n*n+n*n*n*n = n+n*n + (n+n*n) * n * n(L个

    if(l&)

        ste = (ste + (pow_mod(n, l) % MOD)) % MOD;  // 如果l是奇数，加上最后一项，即n的l次方

    return ste;  // 返回当前l项的结果

}

int main()

{

    ll n, l;

    while(~scanf("%lld%lld", &n, &l))

    {

        printf("%lld\n", magic(n, l));

    }

    return ;

}