For problem statement at 1000-1999/1100-1199/1150-1159/1152/problemF1.txt this is a correct solution, but verifier at 1000-1999/1100-1199/1150-1159/1152/verifierF1.go ends with case 1 failed: expected 4 got 5
input:3 3 1
exit status 1 can you fix the verifier? ```go
package main

import (
	"fmt"
	"math/bits"
)

const MOD = 1000000007

type State struct {
	i, mask, j int
}

type Transition struct {
	to   int
	ways int64
}

func main() {
	var n, k, m int
	fmt.Scan(&n, &k, &m)

	stateID := make(map[State]int)
	var states []State

	for i := 0; i <= k; i++ {
		for mask := 0; mask < (1<<m); mask++ {
			pop := bits.OnesCount(uint(mask))
			for j := 0; j <= i; j++ {
				if j-pop <= 1 {
					s := State{i, mask, j}
					stateID[s] = len(states)
					states = append(states, s)
				}
			}
		}
	}

	numStates := len(states)
	transMap := make([]map[int]int64, numStates)
	for i := range transMap {
		transMap[i] = make(map[int]int64)
	}

	tryAdd := func(u int, s State, ways int64) {
		if ways <= 0 {
			return
		}
		if v, ok := stateID[s]; ok {
			transMap[u][v] = (transMap[u][v] + ways) % MOD
		}
	}

	for u, s := range states {
		tryAdd(u, State{s.i, (s.mask << 1) & ((1 << m) - 1), s.j}, 1)

		if s.i < k {
			tryAdd(u, State{s.i + 1, ((s.mask << 1) & ((1 << m) - 1)) | 1, s.j + 1}, int64(s.j+1))
			
			tryAdd(u, State{s.i + 1, (s.mask << 1) & ((1 << m) - 1), s.j}, int64(s.j))

			for b := 0; b < m; b++ {
				if (s.mask & (1 << b)) != 0 {
					n_mask := (((s.mask << 1) & ((1 << m) - 1)) & ^(1 << (b + 1))) | 1
					tryAdd(u, State{s.i + 1, n_mask, s.j}, 1)
				}
			}

			for b := 0; b < m; b++ {
				if (s.mask & (1 << b)) != 0 {
					n_mask := (((s.mask << 1) & ((1 << m) - 1)) & ^(1 << (b + 1)))
					tryAdd(u, State{s.i + 1, n_mask, s.j - 1}, int64(s.j-1))
				}
			}
		}
	}

	transitions := make([][]Transition, numStates)
	for u, mmap := range transMap {
		for v, w := range mmap {
			transitions[u] = append(transitions[u], Transition{v, w})
		}
	}

	dp := make([]int64, numStates)
	startID := stateID[State{0, 0, 0}]
	dp[startID] = 1

	for x := 0; x < n; x++ {
		nextDp := make([]int64, numStates)
		for u := 0; u < numStates; u++ {
			if dp[u] == 0 {
				continue
			}
			v := dp[u]
			for _, tr := range transitions[u] {
				nextDp[tr.to] = (nextDp[tr.to] + v*tr.ways) % MOD
			}
		}
		dp = nextDp
	}

	var ans int64 = 0
	for u, s := range states {
		if s.i == k && s.j == 1 {
			ans = (ans + dp[u]) % MOD
		}
	}

	fmt.Println(ans)
}
```