248. Paint the Fence
MediumDynamic ProgrammingCounting
Paint n posts with k colours so that no more than two adjacent posts have the same colour. Print the number of ways modulo 10⁹ + 7.
Input format
A single line: n k
Output format
The number of ways mod 10⁹ + 7.
Example 1
Input
3 2
Output
6
Example 2
Input
1 1
Output
1
Constraints
1 ≤ n ≤ 10⁵ 1 ≤ k ≤ 10⁵
Read input from standard input and print the answer to standard output. Your code is judged against 5 test cases, most of them hidden.
Loading the MyLoginn IDE…