Input: 'N' = 3, 'K' = 2
Output: 6
Say we have the colors with the numbers 1 and 0. We can paint the fence with 3 posts with the following different combinations.

110
001
101
100
010
011

#define ll long long int
int numberOfWays(int n, int k) 
{
    const int M=1e9+7;
    if(n==1)return k;
    //dp[i][0]-->stores total ways to colour i fences with last two colours same
    //dp[i][1]-->stores total ways to colour i fences with last two colours diff
    ll dp[n+1][2];
    
    //second fence has only 1 choice i.e., to have the same colour as
    //the first one
    dp[2][0]=k;
    //colour first fence with any of the k colours, so choice remaining 
    //for the second fence to be of diff colour is (k-1)
    dp[2][1]=k*(k-1);
    
    for(int i=3;i<=n;i++)
    {
        //we can take all combinations of last two fences painted with diff
        //colour and colour the next fence with the last coloured fence
        //to make last two fences of same colour.
        dp[i][0]=dp[i-1][1];
        
        //we can put all (k-1) colours at the back of all combinations
        //of (i-1)fences except 1 colour(the colour of the (i-1)th fence)
        //for colours of the last two fences to be different
        dp[i][1]=((dp[i-1][0]+dp[i-1][1])%M*(k-1)%M)%M;
    }
    
    ll res=(dp[n][0]+dp[n][1])%M;
    return res;
}