#include <iostream>

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;
}