```go
package main

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

func powMod(a, e, mod int64) int64 {
	res := int64(1)
	for e > 0 {
		if e&1 == 1 {
			res = res * a % mod
		}
		a = a * a % mod
		e >>= 1
	}
	return res
}

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

	var n, k int
	var m int64
	fmt.Fscan(in, &n, &k, &m)

	allowed := make([][]int, k)
	for s := 0; s < k; s++ {
		forbidden := make([]bool, k)
		for x := 0; x < k; x++ {
			if (2*x)%k == s {
				forbidden[x] = true
			}
		}
		for x := 0; x < k; x++ {
			if !forbidden[x] {
				allowed[s] = append(allowed[s], x)
			}
		}
	}

	var unlucky int64
	for s := 0; s < k; s++ {
		dp := make([]int64, k)
		dp[0] = 1
		for i := 0; i < n; i++ {
			ndp := make([]int64, k)
			for sum := 0; sum < k; sum++ {
				v := dp[sum]
				if v == 0 {
					continue
				}
				for _, d := range allowed[s] {
					ns := sum + d
					if ns >= k {
						ns -= k
					}
					ndp[ns] += v
					if ndp[ns] >= m {
						ndp[ns] -= m
					}
				}
			}
			dp = ndp
		}
		unlucky += dp[s]
		unlucky %= m
	}

	total := powMod(int64(k), int64(n), m)
	ans := total - unlucky
	if ans < 0 {
		ans += m
	}
	fmt.Fprintln(out, ans)
}
```