```go
package main

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

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

func gcd(a, b int64) int64 {
	if a < 0 {
		a = -a
	}
	if b < 0 {
		b = -b
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func norm(x, mod int64) int64 {
	x %= mod
	if x < 0 {
		x += mod
	}
	return x
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

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

	if k%2 == 1 {
		g := gcd(k, n-2)
		ans := norm(powMod(k, n, m)-powMod(k-1, n, m), m)
		t := (g - 1) % m
		if n%2 == 0 {
			ans = norm(ans-t, m)
		} else {
			ans = norm(ans+t, m)
		}
		fmt.Fprintln(out, ans)
	} else {
		c := gcd(k/2, n-2)
		kp := powMod(k, n, m)
		a := powMod(k-2, n, m)
		b := powMod(m-2, n, m)
		prod := ((c - 1) % m) * b % m
		temp := norm(kp-a-prod, m)
		inv2 := (m + 1) / 2
		ans := temp * inv2 % m
		fmt.Fprintln(out, ans)
	}
}
```