```go
package main

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

const MOD = 1000000007

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	fmt.Fscan(reader, &t)

	for i := 0; i < t; i++ {
		var n, x, k int64
		fmt.Fscan(reader, &n, &x, &k)
		solve(writer, n, x, k)
	}
}

func solve(w *bufio.Writer, n, x, k int64) {
	// The problem asks for the number of arrays of length n with non-negative integers such that:
	// 1. |a_i - a_{i-1}| <= k
	// 2. At least one element belongs to [x, x+k-1]
	//
	// This can be calculated as:
	// Total valid arrays (conceptually) - Arrays strictly in [0, x-1] - Arrays strictly in [x+k, infinity)
	//
	// The count of valid arrays in [0, m] for large m behaves linearly as A*m + B.
	// Based on combinatorial analysis, the number of "fancy" arrays is given by:
	// (x + k) * (2k + 1)^(n-1) - Count([0, x-1])
	
	// Term 1: (x+k) * (2k+1)^(n-1)
	base := (2*k + 1) % MOD
	term1 := ((x + k) % MOD * modPow(base, n-1)) % MOD

	// Term 2: Count of valid arrays with elements in [0, x-1]
	var term2 int64 = 0
	if x > 0 {
		if k >= x {
			// If k >= x, any transition between elements in [0, x-1] is valid
			// because max diff is (x-1) - 0 < x <= k.
			term2 = modPow(x%MOD, n)
		} else {
			// If k < x, use Matrix Exponentiation to count paths in graph
			size := int(x)
			M := make([][]int64, size)
			for r := 0; r < size; r++ {
				M[r] = make([]int64, size)
				for c := 0; c < size; c++ {
					diff := r - c
					if diff < 0 {
						diff = -diff
					}
					if int64(diff) <= k {
						M[r][c] = 1
					}
				}
			}

			// M^(n-1) gives the number of paths of length n (n-1 transitions)
			// Sum of all elements in M^(n-1) corresponds to starting at any node and ending at any node
			Mn := matPow(M, n-1)
			
			for r := 0; r < size; r++ {
				for c := 0; c < size; c++ {
					term2 = (term2 + Mn[r][c]) % MOD
				}
			}
		}
	}

	ans := (term1 - term2 + MOD) % MOD
	fmt.Fprintln(w, ans)
}

func modPow(base, exp int64) int64 {
	var res int64 = 1
	for exp > 0 {
		if exp&1 == 1 {
			res = (res * base) % MOD
		}
		base = (base * base) % MOD
		exp >>= 1
	}
	return res
}

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

func matPow(A [][]int64, exp int64) [][]int64 {
	size := len(A)
	res := make([][]int64, size)
	for i := 0; i < size; i++ {
		res[i] = make([]int64, size)
		res[i][i] = 1
	}
	base := A
	for exp > 0 {
		if exp&1 == 1 {
			res = matMul(res, base)
		}
		base = matMul(base, base)
		exp >>= 1
	}
	return res
}
```