Paint Fence

A fence has n posts to be painted with k colours so that no more than two adjacent posts have the same colour. Print the number of ways.

1 <= n <= 50 1 <= k <= 10^5