```go
package main

import (
	"io"
	"os"
	"strconv"
	"strings"
)

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	nextInt := func() int {
		for idx < len(data) && (data[idx] < '0' || data[idx] > '9') {
			idx++
		}
		x := 0
		for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
			x = x*10 + int(data[idx]-'0')
			idx++
		}
		return x
	}

	t := nextInt()
	var out strings.Builder

	for ; t > 0; t-- {
		n := nextInt()
		k := nextInt()
		p := int64(nextInt())

		if n == 1 {
			out.WriteString("1\n")
			continue
		}

		inv := make([]int64, k+1)
		if k >= 1 {
			inv[1] = 1
		}
		for i := 2; i <= k; i++ {
			inv[i] = (p - (p/int64(i))*inv[p%int64(i)]%p) % p
		}

		hPrev := make([]int64, k+1)
		hCur := make([]int64, k+1)
		dPrev := make([]int64, k+1)
		dCur := make([]int64, k+1)
		w := make([]int64, k+1)

		for i := 0; i <= k; i++ {
			hPrev[i] = 1
			dPrev[i] = 1
		}

		pow2 := int64(2 % p)

		for level := 2; level <= n; level++ {
			pow2 = pow2 * 2 % p
			r := pow2 - 2
			if r < 0 {
				r += p
			}

			hCur[0] = 1
			for j := 1; j <= k; j++ {
				term := r + int64(j)
				if term >= p {
					term -= p
				}
				hCur[j] = hCur[j-1] * term % p * inv[j] % p
			}

			for i := 0; i <= k; i++ {
				w[i] = 0
			}

			maxT := (k - 1) / 2
			for t0 := 0; t0 <= maxT; t0++ {
				ht := hPrev[t0]
				if ht == 0 {
					continue
				}
				maxS := k - t0
				for s := t0 + 1; s <= maxS; s++ {
					u := s + t0
					w[u] = (w[u] + dPrev[s]*ht) % p
				}
			}

			var pref int64 = 0
			for u := 0; u <= k; u++ {
				pref += w[u]
				if pref >= p {
					pref -= p
				}
				val := pref + pref
				if val >= p {
					val -= p
				}
				dCur[u] = val
			}

			hPrev, hCur = hCur, hPrev
			dPrev, dCur = dCur, dPrev
		}

		out.WriteString(strconv.FormatInt(dPrev[k], 10))
		out.WriteByte('\n')
	}

	os.Stdout.WriteString(out.String())
}
```