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

Difficulty: interview

Starter code:

def two_by_n(n, k):
	

Solutions:
def two_by_n(n, k):
    vv, vh, hv, hh = k-1, (k-1)*(k-2), k-2, (k-1)*(k-2) + 1
    va, ha, vb, hb = 0, 0, 1, 1
    for i in range(n - 1):
        va, ha, vb, hb = vb, hb, vv*vb + vh*ha, hv*vb + hh*ha
    return (k * vb + k*(k-1) * ha) % 12345787


def two_by_n(n, k):
    MOD = 12345787
    x1, x2 = [0, k, k * (k - 1)], [0, 0, k * (k - 1)]
    for _ in range(3, n + 1):
        y1 = (x1[-1] * (k - 1) + x2[-1] * (k - 2)) % MOD
        y2 = (x1[-2] * (k - 1) * (k - 2) + x2[-2] * ((k - 2) * (k - 2) + (k - 1))) % MOD
        x1.append(y1)
        x2.append(y2)
    return (x1[n] + x2[n]) % MOD

import numpy as np
def two_by_n(n,k):
    x=np.array([[k*(k-1),k*(k-1)],[k,0]])
    z=np.array([[k-1,(k-1)*(k-2)],[k-2,k**2-3*k+3]])
    for i in range(n-2):
        x=np.array([np.diag(x@z),x[0]])%12345787
    return sum(x[int(n==1)])%12345787

def two_by_n(n, k):
    if n == 1: return k
    
    n = n-1
    m = 12345787
    x1,x2,x3,x4 = 0, 1, (k-1)*(k-1), k-2
    y1,y2,y3,y4 = 1, 0, 0, 1
    
    while n > 1:
        if n % 2 == 1:
            y1,y2,y3,y4 = (x1*y1 + x2*y3)%m, (x1*y2 + x2*y4)%m, (x3*y1 + x4*y3)%m, (x3*y2 + x4*y4)%m
        p, s = x2 * x3, x1 + x4
        x1,x2,x3,x4 = (x1*x1 + p)%m, x2*s%m, x3*s%m, (p + x4*x4)%m
        n = n // 2
    
    return k * (x1*y1 + x2*y3 + 2*(k-1)*(x1*y2 + x2*y4)) % m

def two_by_n(n, k):
    dp = [[0 for i in range(2)] for j in range(n+1)]
    dp[1][0] = k
    if n < 2:
        print("here")
        return sum(dp[-1])
    dp[2] = [k*(k-1), k*(k-1)]
    # dp[i][0] = one colour at the end, i is the row len
    # dp[i][1] = two colours at the end, i is the row len
    NUM =  12345787
    for i in range(3, n+1):
        dp[i][0] = (max(k-1,0)*dp[i-1][0]+max(k-2,0)*dp[i-1][1]) % NUM
        dp[i][1] = (max(k-1,0)*max(k-2,0)*dp[i-2][0]+(max(k-1,0)+max(k-2,0)*max(k-2,0))*dp[i-2][1]) % NUM
#     print("n = ", n, "k = ", k, "dp = ", dp)  
    return sum(dp[-1]) % NUM

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

def two_by_n(n, k):
    if n==1:
        return k
    F = [0 for k in range(n+1)]
    G = [0 for k in range(n+1)]
    F[1]=1
    F[2]=k-1
    G[2]=1
    for i in range(3, n+1):
        F[i] = (k-1)*F[i-1] +  (k-1)*(k-2)*G[i-1]
        G[i] = (k-2)*F[i-2] +  (k*k-3*k+3)*G[i-2]
    
    return (k*F[n] + k*(k-1)*G[n])%12345787

def two_by_n(n, k):
    op=[[k,0],[k*(k-1),k*(k-1)]]
    for i in range(n-2):
        op.append([op[-1][0]*(k-1) + op[-1][1]*(k-2) ,op[-2][0]*(k-1)*(k-2) + op[-2][1]*(k-1+(k-2)*(k-2))])
    return sum(op[n-1])%12345787

def two_by_n(n, k):
    P = 12345787
    if k == 1: return 1 if n == 1 else 0    
    if n == 1: return k
    if n == 2: return k*(k-1)*2 % P
    f0 = [0] * (n+1)
    f1 = [0] * (n+1)
    f0[1] = k
    f1[1] = 0
    f0[2] = k*(k-1) % P
    f1[2] = k*(k-1) % P
    for i in range(3, n+1):
        f0[i] = (f0[i - 1] * (k-1) + f1[i - 1] * (k-2)) % P
        f1[i] = (f0[i - 2] * (k-1)*(k-2) + f1[i - 2] * (k-1 + (k-2)*(k-2))) % P
    return (f0[n] + f1[n]) % P

def two_by_n(n, k):
    if not n: return 0
    if n==1:  return k
    if n==2:  return 2*k*(k-1)
    a1,a2,b,c = k, 0, k*(k-1), k*(k-1)
    for i in range(n-2):
        a1,a2,b,c = (c, b,
                     a1*(k-1)*(k-2) + a2*((k-1)**2 - (k-2)),
                     c*(k-1) + b*(k-2))
    return (b+c) % 12345787