Painting the Fence

Difficulty: 1400 4000 ms 128 MB

math combinatorics

Paint a row of N planks with K colours so no two adjacent planks share a colour. Count the ways, modulo 10⁹+7.

Input: one line with two integers N and K.

Output: the number of valid colourings mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10¹⁸
• 1 ≤ K ≤ 10⁹

Sample Tests

3 2

2

1 5

5

Read the Editorial