Paint the Fence

Time Limit: 3 sec

 

The Problem

Given a fence with n posts and k colors, find out the number of ways of painting the fence such that at most 2 adjacent posts have the same color. Since answer can be large return it modulo 10^9 + 7.

 

The Input

Each line of input contains two integers n (0<n<=55) and k (0<k<=70). Input is terminated by  EOF.

 

The Output

For each line of input you have to find out the number of ways of painting the fence and show it in a seperate line.

 

Sample Input

2 4

3 6

 

Sample Output

16

6

 

 

Intra University Programming Contest - Winter 2019 [BGC Trust University Bangladesh]

Problem Setter: Parag Paul