':type n: int
:type k: int
:rtype: int'

def numWays(self, n, k):

    if (n == 0):
        return 0
    elif (n == 1):
        return k
    ways = ([0] * 3)
    ways[0] = k
    ways[1] = (((k - 1) * ways[0]) + k)
    for i in xrange(2, n):
        ways[(i % 3)] = ((k - 1) * (ways[((i - 1) % 3)] + ways[((i - 2) % 3)]))
    return ways[((n - 1) % 3)]
