package main

import (
	"io"
	"math"
	"os"
	"strconv"
)

const MOD int64 = 1000000007

type Test struct {
	n int64
	k int
	d int
	e int
}

func powMod(a, e int64) int64 {
	r := int64(1)
	for e > 0 {
		if e&1 == 1 {
			r = r * a % MOD
		}
		a = a * a % MOD
		e >>= 1
	}
	return r
}

func sieve(limit int) []int {
	isComp := make([]bool, limit+1)
	primes := make([]int, 0, 3405)
	for i := 2; i <= limit; i++ {
		if !isComp[i] {
			primes = append(primes, i)
			if i*i <= limit {
				for j := i * i; j <= limit; j += i {
					isComp[j] = true
				}
			}
		}
	}
	return primes
}

func comb(n, r int, fac, ifac []int64) int64 {
	if r < 0 || r > n {
		return 0
	}
	return fac[n] * ifac[r] % MOD * ifac[n-r] % MOD
}

func buildPi(n int64, primes []int) ([]int, []int, []int, int64) {
	sq := int64(math.Sqrt(float64(n)))
	for (sq+1)*(sq+1) <= n {
		sq++
	}
	for sq*sq > n {
		sq--
	}

	id1 := make([]int, int(sq)+1)
	id2 := make([]int, int(sq)+1)
	vals := make([]int64, 0, int(2*sq)+5)
	pi := make([]int, 0, int(2*sq)+5)

	for l := int64(1); l <= n; {
		v := n / l
		vals = append(vals, v)
		pi = append(pi, int(v-1))
		idx := len(vals) - 1
		if v <= sq {
			id1[int(v)] = idx
		} else {
			id2[int(n/v)] = idx
		}
		l = n/v + 1
	}

	m := len(vals)
	cnt := 0
	for _, pv := range primes {
		p := int64(pv)
		p2 := p * p
		if p2 > n {
			break
		}
		for j := 0; j < m; j++ {
			v := vals[j]
			if v < p2 {
				break
			}
			q := v / p
			var idx int
			if q <= sq {
				idx = id1[int(q)]
			} else {
				idx = id2[int(n/q)]
			}
			pi[j] -= pi[idx] - cnt
		}
		cnt++
	}

	return pi, id1, id2, sq
}

func solve(tt Test, primes []int, fac, ifac []int64) int64 {
	if tt.n == 1 {
		return 1
	}

	pw := make([]int64, tt.e+1)
	for i := 1; i <= tt.e; i++ {
		pw[i] = comb(tt.k*i+tt.d, tt.d, fac, ifac)
	}
	c := pw[1]

	piArr, id1, id2, sq := buildPi(tt.n, primes)
	n := tt.n

	getPi := func(x int64) int {
		if x <= sq {
			return piArr[id1[int(x)]]
		}
		return piArr[id2[int(n/x)]]
	}

	var calc func(int64, int) int64
	calc = func(x int64, y int) int64 {
		if x < 2 {
			return 0
		}
		ny := y + 1
		if ny >= len(primes) || int64(primes[ny]) > x {
			return 0
		}
		p0 := int64(primes[ny])
		cnt := getPi(x) - ny
		if cnt <= 0 {
			return 0
		}
		if p0*p0 > x {
			return int64(cnt) * c % MOD
		}

		res := int64(cnt) * c % MOD
		for i := ny; i < len(primes); i++ {
			p := int64(primes[i])
			if p*p > x {
				break
			}
			pe := p
			e := 1
			for pe <= x {
				val := pw[e]
				if e > 1 {
					res += val
					if res >= MOD {
						res -= MOD
					}
				}
				tmp := calc(x/pe, i)
				if tmp != 0 {
					res = (res + val*tmp) % MOD
				}
				if pe > x/p {
					break
				}
				pe *= p
				e++
			}
		}
		return res
	}

	return (1 + calc(n, -1)) % MOD
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	pos := 0
	readInt := func() int64 {
		for pos < len(data) && (data[pos] < '0' || data[pos] > '9') {
			pos++
		}
		var v int64
		for pos < len(data) && data[pos] >= '0' && data[pos] <= '9' {
			v = v*10 + int64(data[pos]-'0')
			pos++
		}
		return v
	}

	t := int(readInt())
	tests := make([]Test, t)
	maxNeed := 1
	for i := 0; i < t; i++ {
		n := readInt()
		k := int(readInt())
		d := int(readInt())
		e := 0
		for x := n; x > 1; x >>= 1 {
			e++
		}
		tests[i] = Test{n: n, k: k, d: d, e: e}
		if n > 1 {
			need := d + k*e
			if need > maxNeed {
				maxNeed = need
			}
		}
	}

	fac := make([]int64, maxNeed+1)
	ifac := make([]int64, maxNeed+1)
	fac[0] = 1
	for i := 1; i <= maxNeed; i++ {
		fac[i] = fac[i-1] * int64(i) % MOD
	}
	ifac[maxNeed] = powMod(fac[maxNeed], MOD-2)
	for i := maxNeed; i >= 1; i-- {
		ifac[i-1] = ifac[i] * int64(i) % MOD
	}

	primes := sieve(31623)

	out := make([]byte, 0, t*12)
	for _, tt := range tests {
		ans := solve(tt, primes, fac, ifac)
		out = strconv.AppendInt(out, ans, 10)
		out = append(out, '\n')
	}
	_, _ = os.Stdout.Write(out)
}