등비수열의 합을 구하는 공식을 이용하여 구하였습니다.
rⁿ (r^{m+1-n-1)/(r-1)}
그런데
마지막 3567404 46749457 21
이데이터에서 오류가 나옵니다
제생각엔 나머지 구하는 부분에서 오차가 나는것같은데
도저히 오차를 수줄이지 못해 질문을 드립니다.
해결해주세요~~ ㅠㅠ

#include <iostream>
#include <cstdlib>
using namespace std;
const unsigned long long int MOD= 1000000007;
long n,m;
long long int c;
bool flag=true;
unsigned long long int BRUTEFORCE(long N)
{
    
    if(N==1)return c;
    if(N%2==0) 
    {
        unsigned long long int a=BRUTEFORCE(N/2);
        
        return (a*a+MOD)%MOD;
    }
    else
    {
        unsigned long long int a=BRUTEFORCE(N-1);
        
        return (a*c+MOD)%MOD;
    }

}
int main()
{
    int T;
    unsigned long long int ans;
    scanf("%d",&T);
    while(T--)
    {
        flag=true;
        cin>>n>>m>>c;
        unsigned long long int b,a;
        if(c==1)
        {
            a=m;
            b=n-1;
            cout<<a-b;
        }
        else
        {
            
            a=(BRUTEFORCE(m+1-n)-1)/(c-1);
            b=BRUTEFORCE(n);
        
            
            ans=(a*b)%MOD;
            
    
        
            
            cout<<ans<<endl;
        }
        
    
    }
}