```
class Solution {
public:
int numWays(int n, int k) {
vector<int> table(n,0);
if(n==0)return 0;
if(k==1&&n>2)return 0;
table[0]=k;
table[1]=k*k;
table[2]=k*k*k-k;
for(int i=3;i<n;i++)
table[i]=table[i-1]*k-(k-1)*table[i-3];
return table[n-1];
}
};
```