# Enter your code here. Read input from STDIN. Print output to STDOUT
MOD = 10 ** 9 + 7

def sieve(n):
    l = [True] * n
    ps = []
    for i in range(2, n):
        if l[i]:
            ps.append(i)
            for j in range(i * i, n, i):
                l[j] = False
    return ps

primes = sieve(10 ** 4)

def pascal(n):
    rows = [[1]]
    for i in range(n):
        rows.append([(a + b) % MOD for (a, b) in zip(rows[-1] + [0], [0] + rows[-1])])
    return rows

binom_ = pascal(3005)
def binom(n, k):
    if k < 0 or k > n: 
        return 0
    return binom_[n][k]
    
def prime_exploration(p, n, d):
    if d == 1: 
        return p ** n
    s = 0
    pp = 1
    for k in range(n + 1):
        s += pp * binom(n - k + d - 2, d - 2)
        pp = p * pp % MOD
    return s % MOD

def divisor_exploration(m, a, d):
    prod = 1
    for i in range(m):
        x = prime_exploration(primes[i], a + i + 1, d)
        prod = prod* x % MOD
    return prod

for i in range(int(input())):
    print(divisor_exploration(*map(int, input().split())))