[[problem:BRUTEFORCE]]

저는 이 문제를 등비수열의 합으로 봤는데요
초항이 start이고 N이 공비라고 두었습니다.
값이 작을 때는 잘나오는거 같은데 커지면 문제가 발생합니다.
MOD연산에서 문제가 발생하는 것 같은데
만약 a/b(mod n) 일때 b하고 n이 서로소 이면 결과값이 상관 없는걸루
알고있는데.. 아닌가요??

#include<cstdio>
#define MOD 1000000007
long long power(long long a, long long b) {
    long long pow = 1;
    while (b){
        if (b & 1){
            pow = (pow * a)%MOD;
            --b;
        }
        a = (a*a)%MOD;
        b = b / 2;
    }
    return pow;
}
int main(){
    freopen("input.txt", "r", stdin);
    int t; scanf("%d", &t);
    while (t--){
        long long ans = 0, start, NpowerR;
        long long a, b, N, sub; scanf("%lld%lld%lld", &a, &b, &N);
        sub = b - a + 1;
        if (N == 1)
            printf("%lld\n", sub);
        else{
            start = power(N, a);
            NpowerR = power(N, sub);
            ans = ((start*((NpowerR - 1)) / (N - 1))) % MOD;
            printf("%lld\n", ans);
        }
    }
}