DP approach to find current state with the help of previous state .
for ( int i = 1 ; i < n ; i ++ ) { dp [ i ] . A = dp [ i - 1 ] . B ; dp [ i ] . B = ( dp [ i - 1 ] . A * ( k - 1 ) ) + ( dp [ i - 1 ] . B * ( k - 2 ) ) ; } cout << dp [ n - 1 ] . A << endl ; return ; }