package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD = 1000000007

func powerMatrix(base [][]int64, exp int64) [][]int64 {
	size := len(base)
	res := make([][]int64, size)
	for i := 0; i < size; i++ {
		res[i] = make([]int64, size)
		res[i][i] = 1
	}
	for exp > 0 {
		if exp%2 == 1 {
			res = multiplyMatrix(res, base)
		}
		base = multiplyMatrix(base, base)
		exp /= 2
	}
	return res
}

func multiplyMatrix(A, B [][]int64) [][]int64 {
	size := len(A)
	res := make([][]int64, size)
	for i := 0; i < size; i++ {
		res[i] = make([]int64, size)
	}
	for i := 0; i < size; i++ {
		for k := 0; k < size; k++ {
			if A[i][k] == 0 {
				continue
			}
			for j := 0; j < size; j++ {
				res[i][j] = (res[i][j] + A[i][k]*B[k][j]) % MOD
			}
		}
	}
	return res
}

func power(base int64, exp int64) int64 {
	res := int64(1)
	base %= MOD
	for exp > 0 {
		if exp%2 == 1 {
			res = (res * base) % MOD
		}
		base = (base * base) % MOD
		exp /= 2
	}
	return res
}

func abs(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var t int
	if _, err := fmt.Fscan(reader, &t); err != nil {
		return
	}
	for i := 0; i < t; i++ {
		var n, x, k int64
		fmt.Fscan(reader, &n, &x, &k)

		A := (x + k) % MOD
		B := power(2*k+1, n-1)
		ans := (A * B) % MOD

		if x > 0 {
			M := make([][]int64, x)
			for r := int64(0); r < x; r++ {
				M[r] = make([]int64, x)
				for c := int64(0); c < x; c++ {
					if abs(r-c) <= k {
						M[r][c] = 1
					}
				}
			}

			M_exp := powerMatrix(M, n-1)
			var C int64 = 0
			for r := int64(0); r < x; r++ {
				for c := int64(0); c < x; c++ {
					C = (C + M_exp[r][c]) % MOD
				}
			}
			ans = (ans - C + MOD) % MOD
		}
		fmt.Println(ans)
	}
}