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

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

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

func countSums(n, k int, allowed []int, mod int64) []int64 {
	dp := make([]int64, k)
	ndp := make([]int64, k)
	dp[0] = 1
	for i := 0; i < n; i++ {
		for j := 0; j < k; j++ {
			ndp[j] = 0
		}
		for s, v := range dp {
			if v == 0 {
				continue
			}
			for _, d := range allowed {
				ns := s + d
				if ns >= k {
					ns -= k
				}
				ndp[ns] += v
				if ndp[ns] >= mod {
					ndp[ns] -= mod
				}
			}
		}
		dp, ndp = ndp, dp
	}
	return dp
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var n, k int
	var m int64
	fmt.Fscan(in, &n, &k, &m)

	base := modPow(int64(k), int64(n-1), m)
	g := (2 - n) % k
	if g < 0 {
		g += k
	}

	var ans int64

	if k%2 == 1 {
		allowed := make([]int, 0, k-1)
		for d := 1; d < k; d++ {
			allowed = append(allowed, d)
		}
		dp := countSums(n, k, allowed, m)
		for x := 0; x < k; x++ {
			t := (g * x) % k
			add := base - dp[t]
			if add < 0 {
				add += m
			}
			ans += add
			if ans >= m {
				ans -= m
			}
		}
	} else {
		half := k / 2
		allowed := make([]int, 0, k-2)
		for d := 0; d < k; d++ {
			if d != 0 && d != half {
				allowed = append(allowed, d)
			}
		}
		dp := countSums(n, k, allowed, m)
		for x := 0; x < half; x++ {
			t := (g * x) % k
			add := base - dp[t]
			if add < 0 {
				add += m
			}
			ans += add
			if ans >= m {
				ans -= m
			}
		}
	}

	fmt.Println(ans % m)
}