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

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Ad-hoc

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]


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])
for n in range(4, 10001):
	m[n] = (15 * m[n - 1] - 32 * m[n - 2] + 15 * m[n - 3] - m[n - 4]) % N