I found an interesting problem on https://www.codewars.com/kata/5a59e029145c46eaac000062:
### Please also check out other katas in [Domino Tiling series](https://www.codewars.com/collections/5d19554d13dba80026a74ff5)!

---

# Task

A domino is a rectangular block with `2` units wide and `1` unit high. A domino can be placed on a grid in two ways: horizontal or vertical.

```
## or #
      #
```

You have infinitely many dominoes, and you want to fill a board that is `N` units wide and `2` units high:

```
<---   N   --->
###############
###############
```

The task is to find **the number of ways** you can fill the given grid with dominoes.

# The Twist

However, you can quickly find that the answer is exactly the Fibonacci series (and yeah, CW has already too many of them), so here is a twist:

Now you have infinite supply of dominoes in `K` colors, and you have to fill the given grid **without any two adjacent dominoes having the same color**. Two dominoes are adjacent if they share an edge.

A valid filling of a 2 x 10 board with three colors could be as follows (note that two same-colored dominoes can share a point):

```
1131223312
2231332212
```

Since the answer will be very large, please give your answer **modulo 12345787**.

# Examples

```python
# K == 1: only one color
two_by_n(1, 1) == 1
two_by_n(3, 1) == 0

# K == 2: two colors
two_by_n(1, 2) == 2
two_by_n(4, 2) == 4
two_by_n(7, 2) == 2

# K == 3: three colors
two_by_n(1, 3) == 3
two_by_n(2, 3) == 12
two_by_n(5, 3) == 168 # yes, the numbers grow quite quickly

# You must handle big values
two_by_n(10, 5) == 7802599
two_by_n(20, 10) == 4137177
```

# Constraints

`1 <= N <= 10000`

`1 <= K <= 100`

All inputs are valid integers.

I tried it in Python, but could not do it. Can you solve it?
def two_by_n(n, k):
    mod = 12345787
    if n == 0: return 0
    elif n == 1: return k
    d = [k, 0, k * (k - 1), k * (k - 1)]
    for i in range(3, n + 1):
        x, y, z, w = d
        d = [z, w, (z * (k - 1) + w * (k - 2)) % mod, (x * (k - 1) * (k - 2) + y * ((k - 2)**2 + k - 1)) % mod]
    return (d[2] + d[3]) % mod