Count colorings of a row of houses with fixed end colors

A contractor is repainting a row of n houses, numbered 0 to n - 1. There are k paint colors, numbered 0 to k - 1.

The new paint job must follow two rules:

• Two neighboring houses (i and i + 1) never have the same color.
• House 0 must be painted first and house n - 1 must be painted last. Both colors are given.

Implement:

def count_ways(n: int, k: int, first: int, last: int) -> int:
    ...

Return the number of valid colorings modulo 10^9 + 7. If no coloring is valid (for example, a color is out of range), return 0.

Constraints

• 1 <= n <= 10^18
• 1 <= k <= 10^9
• first and last are integers. They may be outside 0..k-1.
• When n == 1, house 0 is both the first and the last house.

Example 1

n = 3, k = 3, first = 0, last = 0  ->  2

The valid rows are 0 1 0 and 0 2 0.

Example 2

n = 4, k = 3, first = 0, last = 2  ->  3

The valid rows are 0 1 0 2, 0 2 0 2, and 0 2 1 2.

Start with an approach that works for n up to 10^5, then make it fast enough for n = 10^18.