Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.