¬ just serendipity 🍀 (not just serendipity)

class Solution:
    def numWays(self, n: int, k: int) -> int:
        from functools import cache

        @cache
        def solve(n):
            if n <= 0:
                return 0

            if n == 1:
                return k

            if n == 2:
                return k ** 2

            return (k - 1) *  (solve(n - 1) + solve(n - 2))

        return solve(n)