```
class Solution {
public:
int numWays(int n, int k) {
if(n == 0 || k == 0) {
return 0;
}
if(n == 1) {
return k;
}
int prev = 1;
int cur = k;
for(int i = 2 ; i < n ; ++i) {
int tmp = (k - 1) * (prev + cur);
prev = cur;
cur = tmp;
}
return k * cur;
}
};
```