[[problem:BRUTEFORCE]] 풀고 있는데 시간초과가 자꾸 나오네요.

끄적끄적 해서 다음과 같이 점화식을 세웠습니다.

solve(start,end,n) =
solve(start,(start+end-1)/2,n) +
(n^(end-start+1/2))*solve(start,(start+end-1)/2,n)

코드는 아래와 같이 작성했는데..
답은 맞게 나오는데 시간초과로 패쓰를 못하고 있네요;;
최적화 포인트가 더 있는건가요?
미리 감사드립니다.

~~~ c++
#include

using namespace std;
const int MOD = 1000000007;

// 최소자리수 start, 최대자리수 end, 문자 수 n 일때,
// 모든 가짓수를 구한다.
long long solve(int start, int end, int n)
{
// 기저사례
if (n == 1) return end - start + 1;
if (start > end) return 0;
if (start == end) {
long long ret = 1;
for (int i = 0; i < start; i++)
ret = (ret * n) % MOD;
return ret;
}

// 갯수가 홀수인 경우는 맨 뒤를 하나 제낀다.
bool odd = false;
if ((end - start + 1) % 2 == 1) {
    --end;
    odd = true;
}

// 반으로 나누고 앞에꺼 계산
// solve(start, (start + end - 1) / 2)
long long ret = 0;
int mid = (start + end - 1) / 2;
ret = solve(start, mid, n);
ret %= MOD;

// 뒤에꺼는 앞에꺼 계산 결과를 이용해서 구한다.
// (n ^ ((end - start + 1) / 2)) * solve(start, (start + end - 1) / 2)
long long ret2 = 1;
int mid2 = (end - start + 1) / 2;
for (int i = 0; i < mid2; i++)
    ret2 = (ret2 * n) % MOD;
ret += ret2 * ret;
ret %= MOD;

// 홀수인 경우에 처음에 제낀것을 계산하여 더한다.
if (odd) {
    for (int i = mid2; i < end + 1; i++)
        ret2 = (ret2 * n) % MOD;
    ret += ret2;
    ret %= MOD;
}

return ret;

}

int main(int c, char **v)
{
ios_base::sync_with_stdio();
int C;
cin >> C;
while (C--) {
int A, B, N;
cin >> A >> B >> N;
cout << solve(A, B, N) << endl;
}
return 0;
}

<spoiler>