Avoid Prefix Palindromes

main.kt

const val INF : Long = 1000 * 1000 * 1000 + 9

// n^k
fun pow(n: Long, k: Int): Long =
        when
        {
            k == 0 -> 1L
            (k % 2) == 0 ->
            {
                val x = pow(n, k / 2)
                (x * x) % INF
            }
            else -> (pow(n, k - 1) * n) % INF
        }

fun main(args: Array<String>)
{
    val input = readLine()!!.split(" ").map { Integer.parseInt(it) }.toList()
    val n = input[0]
    val k = input[1].toLong()

    val dp = LongArray(n + 1)
    dp[1] = k
    var sumK = 0L

    for (v in 2..n)
    {
        if (v % 2 == 1)
        {
            sumK = (sumK * k + dp[v / 2 + 1]) % INF
        }
        dp[v] = (INF + pow(k, (v + 1) / 2) - sumK) % INF
    }

    println(dp[n])
}