Painting the Fence
easyDynamic Programming II+10 XPTime limit 2s
You paint a fence of n posts in a row, using any of k colours for each post. To keep it pretty, no three consecutive posts may have the same colour (two in a row is fine). How many ways are there to paint the fence? Print the count modulo 1 000 000 007.
Input: one line n k.
Output: the number of ways modulo 10⁹ + 7.
Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁵.
Think about it: split the ways by how the fence ends: same = the last two posts share a colour, diff = the last two differ. A new post either copies the last colour (allowed only after diff) or picks one of the other k − 1 colours (after either). So same' = diff and diff' = (same + diff) · (k − 1).
Sample input 1
3 2
Sample output 1
6
Sample input 2
1 5
Sample output 2
5
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).