For problem statement at 1000-1999/1800-1899/1800-1809/1808/problemE2.txt this is a correct solution, but verifier at 1000-1999/1800-1899/1800-1809/1808/verifierE2.go ends with All tests passed can you fix the verifier? package main

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

func powMod(a, e, mod int64) int64 {
	a %= mod
	res := int64(1 % mod)
	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 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	var n, k, m int64
	fmt.Fscan(in, &n, &k, &m)

	kn := powMod(k, n, m)

	if k%2 == 1 {
		d := n - 2
		if d < 0 {
			d = -d
		}
		g := gcd(d, k)
		ans := kn - powMod(k-1, n, m)
		t := (g - 1) % m
		if n%2 == 0 {
			ans -= t
		} else {
			ans += t
		}
		ans %= m
		if ans < 0 {
			ans += m
		}
		fmt.Println(ans)
	} else {
		d := n - 2
		if d < 0 {
			d = -d
		}
		g := gcd(d, k/2)
		ans := kn - powMod(k-2, n, m)
		t := powMod(2, n, m) * ((g - 1) % m) % m
		if n%2 == 0 {
			ans -= t
		} else {
			ans += t
		}
		ans %= m
		if ans < 0 {
			ans += m
		}
		inv2 := (m + 1) / 2
		ans = ans * inv2 % m
		fmt.Println(ans)
	}
}