Palindromey II

A palindrome of length $n$ is a sequence of characters $a_1a_2\dots a_n$ such that for all $1 \leq i \leq n$, $a_i = a_{(n+1)-i}$. Assuming $1 \leq a_i \leq k$ for all $i$ and $n$ is odd, find the number of palindromes of length $n$ when $n = 9$ and $k = 6$.