```go
package main

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

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

	const MOD = 1000000007

	// State encoding:
	// j (4 bits) | F (1 bit) | c0 (4 bits) | c1 (4 bits) | c2 (4 bits) | c3 (4 bits)
	// Fits in 21 bits. Array size 2^21.
	const SIZE = 1 << 21
	dp := make([]int, SIZE)
	newDp := make([]int, SIZE)

	active := make([]int, 0, 10000)
	newActive := make([]int, 0, 10000)

	// Initial state: 0 nodes, 0 finished, 0 active components
	dp[0] = 1
	active = append(active, 0)

	// Fixed array for counts to avoid allocation in loop
	var c [4]int
	var nextC [4]int

	for i := 1; i <= n; i++ {
		newActive = newActive[:0]

		for _, state := range active {
			ways := dp[state]
			dp[state] = 0 // Clear for next iteration (reuse array)
			if ways == 0 {
				continue
			}

			// Decode
			j := state & 0xF
			f := (state >> 4) & 1
			activeComps := 0
			for d := 0; d < m; d++ {
				val := (state >> (5 + 4*d)) & 0xF
				c[d] = val
				activeComps += val
			}

			// Count of components about to expire (distance m-1 from current i -> distance m from i+1)
			remExp := c[m-1]

			// Helper to add transition to new state
			// defined inline to capture newActive, newDp, k, m, MOD
			addState := func(nj, nf int, nc *[4]int) {
				// Calculate ntotal for pruning
				ntotal := nf
				for d := 0; d < m; d++ {
					ntotal += nc[d]
				}
				
				// Pruning: need ntotal-1 merges to reach 1 component
				// Each merge consumes a node. Remaining nodes: k - nj
				if ntotal > k - nj + 1 {
					return
				}

				// Encode
				enc := nj | (nf << 4)
				for d := 0; d < m; d++ {
					enc |= (nc[d] << (5 + 4*d))
				}

				if newDp[enc] == 0 {
					newActive = append(newActive, enc)
				}
				newDp[enc] = (newDp[enc] + ways) % MOD
			}

			// --- Action 1: Skip node i ---
			{
				valid := true
				nextF := f
				if remExp > 0 {
					// Components expiring must become finished
					if remExp > 1 || f == 1 {
						valid = false // Can't have >1 finished components
					} else {
						nextF = 1
					}
				}
				if valid {
					// Shift counts: dist d -> d+1
					for d := 0; d < m-1; d++ {
						nextC[d+1] = c[d]
					}
					nextC[0] = 0
					addState(j, nextF, &nextC)
				}
			}

			if j < k {
				// --- Action 2: Include node i ---

				// 2a. Start New Component: (i)
				{
					valid := true
					nextF := f
					if remExp > 0 {
						if remExp > 1 || f == 1 {
							valid = false
						} else {
							nextF = 1
						}
					}
					if valid {
						for d := 0; d < m-1; d++ {
							nextC[d+1] = c[d]
						}
						nextC[0] = 1
						addState(j+1, nextF, &nextC)
					}
				}

				// 2b. Append to existing component: ... -> e -> i
				for src := 0; src < m; src++ {
					count := c[src]
					if count == 0 {
						continue
					}
					
					// If we append to a component in bucket src, it updates to dist 0.
					// Components in bucket m-1 expire unless picked.
					
					currRemExp := remExp
					if src == m-1 {
						currRemExp--
					}
					
					valid := true
					nextF := f
					if currRemExp > 0 {
						if currRemExp > 1 || f == 1 {
							valid = false
						} else {
							nextF = 1
						}
					}
					
					if valid {
						for d := 0; d < m-1; d++ {
							cnt := c[d]
							if d == src {
								cnt--
							}
							nextC[d+1] = cnt
						}
						nextC[0] = 1
						
						oldWays := ways
						ways = int((int64(ways) * int64(count)) % int64(MOD))
						addState(j+1, nextF, &nextC)
						ways = oldWays
					}
				}

				// 2c. Prepend to existing component: i -> s -> ...
				totalComps := activeComps + f
				if totalComps > 0 {
					// End does not change, just shifts
					valid := true
					nextF := f
					if remExp > 0 {
						if remExp > 1 || f == 1 {
							valid = false
						} else {
							nextF = 1
						}
					}
					if valid {
						for d := 0; d < m-1; d++ {
							nextC[d+1] = c[d]
						}
						nextC[0] = 0
						
						oldWays := ways
						ways = int((int64(ways) * int64(totalComps)) % int64(MOD))
						addState(j+1, nextF, &nextC)
						ways = oldWays
					}
				}

				// 2d. Merge two components: ... -> e -> i -> s -> ...
				if totalComps >= 2 {
					for src := 0; src < m; src++ {
						count := c[src]
						if count == 0 {
							continue
						}
						
						// Src component merges into another. Src disappears from counts.
						currRemExp := remExp
						if src == m-1 {
							currRemExp--
						}
						
						valid := true
						nextF := f
						if currRemExp > 0 {
							if currRemExp > 1 || f == 1 {
								valid = false
							} else {
								nextF = 1
							}
						}
						
						if valid {
							for d := 0; d < m-1; d++ {
								cnt := c[d]
								if d == src {
									cnt--
								}
								nextC[d+1] = cnt
							}
							nextC[0] = 0
							
							oldWays := ways
							mult := int64(count) * int64(totalComps - 1)
							ways = int((int64(ways) * mult) % int64(MOD))
							addState(j+1, nextF, &nextC)
							ways = oldWays
						}
					}
				}
			}
		}
		
		dp, newDp = newDp, dp
		active, newActive = newActive, active
	}

	ans := 0
	for _, state := range active {
		j := state & 0xF
		if j != k {
			continue
		}
		f := (state >> 4) & 1
		activeComps := 0
		for d := 0; d < m; d++ {
			activeComps += (state >> (5 + 4*d)) & 0xF
		}
		// Valid full path must be 1 component (either finished or active)
		if activeComps + f == 1 {
			ans = (ans + dp[state]) % MOD
		}
	}
	fmt.Println(ans)
}
```