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)

		
		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
		}

		
		
		waysVal := make([][]int64, n+1)
		for h := 1; h <= n; h++ {
			waysVal[h] = make([]int64, k_target+1)
			
			
			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++ {
				
				num := (sizeMod + int64(val) - 1 + p) % p
				waysVal[h][val] = combinations(num, val)
			}
		}

		
		
		
		
		
		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)
			}
		}

		
		
		for val := 0; val <= k_target; val++ {
			oldDP[val][1][0] = 1 
			oldDP[val][2][0] = 1
		}

		
		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)
			}
		}
		
		
		prefOld := make([][]int64, 3) 
		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++ {
			
			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
					}
				}
			}

			
			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
			}

			
			for i := 1; i <= k_target; 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 := 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]

					
					val1 := d1_L * ways_R % p * 2 % p
					
					
					
					
					
					
					
					
					
					
					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
					
					
					
					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
					}
				}
			}
			
			
			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
					}
				}
			}
			
			
			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()
}