```
class Solution(object):
def numWays(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
#ary1 ith == i-1th ary2 ith != i-1th
#ary1[i] = ary2[i - 1] ary2[i] = (k - 1) * ary1[i - 1] + ary2[i - 1] * (k - 1)
if n == 0:
return 0
if n <= 2:
return k ** n
eqary, neqary = [ 0 for i in xrange(n) ], [ 0 for i in xrange(n) ]
for i in xrange(n):
eqary[i] = k if i == 0 or i == 1 else neqary[i - 1]
neqary[i] = k if i == 0 else (k * (k - 1) if i == 1 else (k - 1) * (eqary[i - 1] + neqary[i - 1] ) )
return eqary[-1] + neqary[-1]
```