```go
package main

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

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

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

	for idx := 0; idx < t; idx++ {
		var n, k_target int
		var p int64
		fmt.Fscan(reader, &n, &k_target, &p)

		// Precompute modular inverse for combinations
		inv := make([]int64, k_target+1)
		if k_target >= 1 {
			inv[1] = 1
			for i := 2; i <= k_target; i++ {
				inv[i] = (p - p/int64(i)) * inv[p%int64(i)] % p
			}
		}
		
		combinations := func(N int64, K int) int64 {
			if K < 0 {
				return 0
			}
			if K == 0 {
				return 1
			}
			N %= p
			res := int64(1)
			for i := 0; i < K; i++ {
				term := (N - int64(i) + p) % p
				res = res * term % p
				res = res * inv[i+1] % p
			}
			return res
		}

		// Cache ways(h, k)
		// ways_cache[h][k] stores number of ways to assign sums in a height h tree summing to k
		waysVal := make([][]int64, n+1)
		for h := 1; h <= n; h++ {
			waysVal[h] = make([]int64, k_target+1)
			
			// Calculate (2^h - 1) % p
			sizeMod := int64(1)
			base := int64(2)
			exp := h
			for exp > 0 {
				if exp%2 == 1 {
					sizeMod = sizeMod * base % p
				}
				base = base * base % p
				exp /= 2
			}
			sizeMod = (sizeMod - 1 + p) % p
			
			for val := 0; val <= k_target; val++ {
				// We need binom(size + val - 1, val)
				num := (sizeMod + int64(val) - 1 + p) % p
				waysVal[h][val] = combinations(num, val)
			}
		}

		// DP state: [k][m][next_val_idx]
		// m: 1 or 2
		// next_val_idx: 0 maps to -1, 1..k+1 maps to 0..k
		// size: K+2
		
		oldDP := make([][][]int64, k_target+1)
		for i := range oldDP {
			oldDP[i] = make([][]int64, 3)
			for m := 1; m <= 2; m++ {
				oldDP[i][m] = make([]int64, k_target+2)
			}
		}

		// Base case h=1
		// Leaves have next_val = -1 (index 0), support any number of pops
		for val := 0; val <= k_target; val++ {
			oldDP[val][1][0] = 1 
			oldDP[val][2][0] = 1
		}

		// Buffers
		newDP := make([][][]int64, k_target+1)
		for i := range newDP {
			newDP[i] = make([][]int64, 3)
			for m := 1; m <= 2; m++ {
				newDP[i][m] = make([]int64, k_target+2)
			}
		}
		
		delta := make([][][]int64, k_target+1)
		for i := range delta {
			delta[i] = make([][]int64, 3)
			for m := 1; m <= 2; m++ {
				delta[i][m] = make([]int64, k_target+2)
			}
		}
		
		// Helper arrays
		prefOld := make([][]int64, 3) // [m][w_idx]
		for m := 1; m <= 2; m++ {
			prefOld[m] = make([]int64, k_target+2)
		}
		sumOld := make([]int64, 3)
		totalD1 := make([]int64, k_target+1)

		for h := 2; h <= n; h++ {
			// Clear delta
			for i := 0; i <= k_target; i++ {
				for m := 1; m <= 2; m++ {
					for w := 0; w <= k_target+1; w++ {
						delta[i][m][w] = 0
					}
				}
			}

			// Precompute TotalD1 for all sums (sum over next_vals)
			for x := 0; x <= k_target; x++ {
				var s int64 = 0
				for w := 0; w <= k_target+1; w++ {
					s = (s + oldDP[x][1][w]) % p
				}
				totalD1[x] = s
			}

			// Iterate winner sum i
			for i := 1; i <= k_target; i++ {
				// Compute prefix sums for Left child (winner) with sum i
				for m := 1; m <= 2; m++ {
					var s int64 = 0
					for w := 0; w <= k_target+1; w++ {
						s = (s + oldDP[i][m][w]) % p
						prefOld[m][w] = s
					}
					sumOld[m] = s
				}
				
				d1_L := sumOld[1]
				
				// Limit for loser sum j: j < i and i + j <= k_target
				limit := k_target - i
				if i-1 < limit {
					limit = i - 1
				}

				for j := 0; j <= limit; j++ {
					ways_R := waysVal[h-1][j]
					d1_R := totalD1[j]

					// Term for m=1: 2 * D1(Left) * Ways(Right)
					val1 := d1_L * ways_R % p * 2 % p
					
					// Term for m=2:
					// If next_val_Left > j: Left needs D2, Right needs Ways
					// If next_val_Left < j: Left needs D1, Right needs D1
					
					// Indices mapping: value v maps to v+1. -1 maps to 0.
					// Comparison with j:
					// v > j => index > j+1
					// v < j => index <= j (actually index < j+1, which includes -1 if j>=0)
					
					idx_j := j + 1
					var sum_large int64
					if idx_j > k_target+1 {
						sum_large = 0
					} else {
						sum_large = (sumOld[2] - prefOld[2][idx_j] + p) % p
					}
					
					var sum_small int64
					if idx_j-1 >= 0 {
						sum_small = prefOld[1][idx_j-1]
					} else {
						sum_small = 0
					}
					
					term2 := (sum_large * ways_R % p) + (sum_small * d1_R % p)
					val2 := term2 % p * 2 % p
					
					// Add to delta at k = i+j
					// Next value of current tree is i (mapped i+1)
					if val1 != 0 {
						delta[i+j][1][i+1] = (delta[i+j][1][i+1] + val1) % p
					}
					if val2 != 0 {
						delta[i+j][2][i+1] = (delta[i+j][2][i+1] + val2) % p
					}
				}
			}
			
			// Apply Delta
			for m := 1; m <= 2; m++ {
				for w := 0; w <= k_target+1; w++ {
					var cur int64 = 0
					for k := 0; k <= k_target; k++ {
						cur = (cur + delta[k][m][w]) % p
						newDP[k][m][w] = cur
					}
				}
			}
			
			// Swap old, new
			oldDP, newDP = newDP, oldDP
		}
		
		var ans int64 = 0
		for w := 0; w <= k_target+1; w++ {
			ans = (ans + oldDP[k_target][2][w]) % p
		}
		fmt.Fprintln(writer, ans)
	}
}

func main() {
	solve()
}
```