import sys
# sys.stdin = open('cases/bruteforce.txt')


cache = dict()


def normalize(num):
    if num >= 1000000007:
        num %= 1000000007
    return num


for c in range(int(input())):
    A, B, N = list(map(int, input().split()))

    # AB 길이
    ab_len = B - A + 1

    # 초기화
    s = 0
    i = 0

    # 첫번째 항
    p = N
    s += p
    i += 1

    # 일정항 까지의 합을 저장해둠. (마지막 연산을 위해서)
    cache = dict()
    cache[1] = N

    while True:
        if i << 1 > ab_len:

            # 마지막 연산
            rest = ab_len - i
            rest_arr = list(bin(rest)[2:])
            i = 1
            s_part = 0
            for j in list(reversed(rest_arr)):
                if j == '1':
                    s_part += cache[i]
                i <<= 1
            tmp = p * s_part
            tmp = normalize(tmp)
            s += tmp
            s = normalize(s)
            break

        else:
            tmp = p * s
            tmp = normalize(tmp)
            s += tmp
            s = normalize(s)
            i <<= 1
            cache[i] = s
            p = pow(p, 2)
            p = normalize(p)

    # TODO: 최적화 해야함
    # N 을 A - 1 번 곱한다.
    base = 1
    if A != 1:
        base = 1
        for i in range(1, A):
            base *= N
            base = normalize(base)
    print(normalize(s * base))

# 기본 풀이
# for c in range(int(input())):
#     A, B, N = list(map(int, input().split()))
#     a = pow(N, A)
#     b = 1
#     c = 1
#     for i in range(1, B - A + 1):
#         c *= N
#         b += c
#         normalize(b)
#     print(normalize(a * b))