```
int numWays(int n, int k) {
if (n == 0) return 0;
if (n <= 2) return pow(k, n);
int same = k, notSame = k * (k-1);
for(int i=3; i <= n; ++i){
int oldSame = same;
same = notSame;
notSame = (oldSame + notSame) * (k-1);
}
return same + notSame;
}
```