### 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 `2*N` units wide and `5` units high:

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

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

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

# Examples

```python
five_by_2n(1) == 8
five_by_2n(2) == 95
five_by_2n(3) == 1183
five_by_2n(5) == 185921

five_by_2n(10) == 8228892
five_by_2n(20) == 9942990
five_by_2n(50) == 2308182
five_by_2n(100) == 334896

five_by_2n(1000) == 6032838
five_by_2n(10000) == 2392948
```

# Constraints

`1 <= N <= 10000`

All inputs are valid integers.

# Hint

The reference solution uses eleven mutual recurrence equations.

Difficulty: interview

Starter code:

def five_by_2n(n):
	

Solutions:
import numpy as np
def five_by_2n(n):
    x=np.array([[1,1,1,1,1,1,1,1],[1,2,1,1,1,2,2,1],[1,1,2,1,1,1,2,1],[1,1,1,2,1,1,2,1],[1,1,1,1,2,1,2,2],[1,2,1,1,2,1,6,1],[1,2,1,1,2,1,6,1],[1,2,1,1,2,1,6,1]])
    y=np.array([1,1,1,1,1,1,1,1])
    z=y
    for i in range(n-1):
        z=np.mod(x@z,12345787*y)
    return z.T@y%12345787

mod=12345787
memo=[0,8,95,1183,14824]
for i in range(10**5): memo.append((15*memo[-1]-32*memo[-2]+15*memo[-3]-memo[-4])%mod);
def five_by_2n(n): return memo[n]

a=[3];b=[1];c=[2];d=[1];e=[2];f=[3];g=[1];h=[1];i=[1];j=[8]

for _ in range(10000):
    next_a = 3*a[-1] + b[-1] + e[-1] + f[-1] + h[-1] + i[-1] + 3*j[-1]
    next_b = a[-1] + 2*b[-1] + e[-1] + i[-1] + j[-1]
    next_c = 2*c[-1] + d[-1] + f[-1] + g[-1] + 2*j[-1]
    next_d = c[-1] + 2*d[-1] + f[-1] + g[-1] + j[-1]
    next_e = a[-1] + b[-1] + 2*e[-1] + i[-1] + 2*j[-1]
    next_f = a[-1] + c[-1] + d[-1] + 3*f[-1] + g[-1] + h[-1] + 3*j[-1]
    next_g = c[-1] + d[-1] + f[-1] + g[-1] + j[-1]
    next_h = a[-1] + f[-1] + h[-1] + j[-1]
    next_i = a[-1] + b[-1] + e[-1] + i[-1] + j[-1]
    next_j = 3*a[-1] + b[-1] + 2*c[-1] + d[-1] + 2*e[-1] + 3*f[-1] + g[-1] + h[-1] + i[-1] + 8*j[-1]
    a.append(next_a%12345787)
    b.append(next_b%12345787)
    c.append(next_c%12345787)
    d.append(next_d%12345787)
    e.append(next_e%12345787)
    f.append(next_f%12345787)
    g.append(next_g%12345787)
    h.append(next_h%12345787)
    i.append(next_i%12345787)
    j.append(next_j%12345787)
    
def five_by_2n(n):
    return j[n-1]

MOD = 12345787
MSK = 1 << 5
ANS = [1]
FLAG = False

def trans(T, x):
    y = [0 for i in range(MSK)]
    for i in range(MSK):
        for j in T[i]:
            y[j] += x[i]
    for i in range(MSK):
        y[i] %= MOD
    return y

def prework(MAXN=10010):
    nonlocal FLAG
    if FLAG:
        return
    FLAG = True
    T = [[] for i in range(MSK)]
    for i in range(MSK):
        for j in range(MSK):
            if (i & j) == 0:
                rm = (MSK - 1) ^ (i | j)
                p = [k for k in range(5) if ((rm >> k) & 1) == 1]
                flag = (len(p) % 2 == 0)
                if flag:
                    for k in range(len(p) // 2):
                        flag &= (p[2 * k] + 1 == p[2 * k + 1])
                if flag:
                    T[i].append(j)
    x = [0 for i in range(MSK)]
    x[0] = 1
    nonlocal ANS
    for i in range(2 * MAXN):
        x = trans(T, x)
        if i % 2 == 1:
            ANS.append(x[0])

def five_by_2n(n):
    prework()
    nonlocal ANS
    return ANS[n]

# https://www.codeleading.com/article/49772209610/
arr=[0, 8, 95, 1183, 14824]

for i in range(0, 10**5): 
    arr.append((15 * arr[-1] - 32 * arr[-2] + 15 * arr[-3] - arr[-4]) % 12345787)

def five_by_2n(n): 
    return arr[n]

def five_by_2n(n):
    a1, a2, a3, a4 = 1, 8, 95, 1183
    
    for i in range(n):     
        nxt = (15 * a4 - 32 * a3 + 15 * a2 - a1) % 12345787
        a1, a2, a3, a4 = a2, a3, a4, nxt
    
    return a1

def five_by_2n(n):
    a = [1, 8, 95, 1183, 14824]
    
    while len(a) <= n:
        nxt = (15 * a[-1] - 32 * a[-2] + 15 * a[-3] - a[-4])  % 12345787
        a.append(nxt)
    
    return a[n]

def five_by_2n(n):
    def b(n):
        dp = [0] * n
        dp[:8] = [0, 8, 0, 95, 0, 1183, 0, 14824]
        for i in range(8, n):
            dp[i] = 15 * dp[i - 2] - 32 * dp[i - 4] + 15 * dp[i - 6] - dp[i - 8]
        return dp[-1] % 12345787
    if n<=8:
        return {1:8, 2:95, 3:1183, 4:14824, 5:185921, 6:2332097, 7:4561586,8:8916464}[n]
    else:
        return b(2*n)

def five_by_2n(n):
    b = [8, 95, 1183, 14824]
    if n <= 4:
        return b[n - 1]
    for i in range(4,n):
        b.append((15*b[i-1] - 32*b[i-2] + 15*b[i-3] - b[i-4])%12345787)
    return b[-1]


N,m,five_by_2n=12345787,{0:1,1:8,2:95,3:1183},lambda n:m[n]            # set
for n in range(4,10001):m[n]=(15*m[n-1]-32*m[n-2]+15*m[n-3]-m[n-4])%N  # build