package main

import (
	"fmt"
)

func solveK(n, h, k int) int64 {
	type State struct {
		x [4]int
	}
	states := []State{}
	stateToID := make(map[State]int)

	var generate func(idx int, maxVal int, current State)
	generate = func(idx int, maxVal int, current State) {
		if idx == k {
			stateToID[current] = len(states)
			states = append(states, current)
			return
		}
		for v := maxVal; v >= 0; v-- {
			current.x[idx] = v
			generate(idx+1, v, current)
		}
	}

	var startState State
	generate(0, h-1, startState)

	numStates := len(states)
	outTrans := make([]int, numStates)
	inTrans := make([][]int, numStates)
	for i := range inTrans {
		inTrans[i] = make([]int, k)
	}

	for id, s := range states {
		outS := State{}
		valid := true
		for i := 0; i < k; i++ {
			outS.x[i] = s.x[i] + 1
			if outS.x[i] >= h {
				valid = false
			}
		}
		if valid {
			outTrans[id] = stateToID[outS]
		} else {
			outTrans[id] = -1
		}

		for m := 0; m < k; m++ {
			inS := State{}
			validIn := true
			var newGaps [4]int
			for i := 0; i < k; i++ {
				if i == m {
					newGaps[i] = 0
				} else {
					g := s.x[i] + 1
					if g >= h {
						validIn = false
					}
					newGaps[i] = g
				}
			}
			if validIn {
				for i := 0; i < k; i++ {
					for j := i + 1; j < k; j++ {
						if newGaps[i] < newGaps[j] {
							newGaps[i], newGaps[j] = newGaps[j], newGaps[i]
						}
					}
				}
				for i := 0; i < k; i++ {
					inS.x[i] = newGaps[i]
				}
				inTrans[id][m] = stateToID[inS]
			} else {
				inTrans[id][m] = -1
			}
		}
	}

	type Trans struct {
		dest int
		mult int64
	}
	transitions := make([][]Trans, numStates)
	for id := 0; id < numStates; id++ {
		var dests []int
		var mults []int64
		add := func(dest int, count int64) {
			for i, d := range dests {
				if d == dest {
					mults[i] += count
					return
				}
			}
			dests = append(dests, dest)
			mults = append(mults, count)
		}
		if outTrans[id] != -1 && 4-k > 0 {
			add(outTrans[id], int64(4-k))
		}
		for m := 0; m < k; m++ {
			if inTrans[id][m] != -1 {
				add(inTrans[id][m], 1)
			}
		}
		for i, d := range dests {
			transitions[id] = append(transitions[id], Trans{d, mults[i]})
		}
	}

	dp := make([]int64, numStates)
	var initS State
	dp[stateToID[initS]] = 1

	for step := 0; step < n; step++ {
		nextDp := make([]int64, numStates)
		for id, ways := range dp {
			if ways == 0 {
				continue
			}
			for _, t := range transitions[id] {
				nextDp[t.dest] = (nextDp[t.dest] + ways*t.mult) % 1000000009
			}
		}
		dp = nextDp
	}

	var total int64 = 0
	for _, ways := range dp {
		total = (total + ways) % 1000000009
	}
	return total
}

func main() {
	var n, h int
	if _, err := fmt.Scan(&n, &h); err != nil {
		return
	}

	n1 := solveK(n, h, 1)
	n2 := solveK(n, h, 2)
	n3 := solveK(n, h, 3)
	n4 := solveK(n, h, 4)

	ans := (4*n1 - 6*n2 + 4*n3 - n4) % 1000000009
	if ans < 0 {
		ans += 1000000009
	}

	fmt.Println(ans)
}