```
def __init__(self):
self.ways = {}
def numWays(self, n, k):
# Each step depends on number of ways from the previous two steps.
self.ways = {0:0, 1:k, 2:k**2}
return self.nways(n, k)
def nways(self, n, k):
if n not in self.ways:
self.ways[n] = (k-1)*(self.nways(n-1,k) + self.nways(n-2,k))
return self.ways[n]
```