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

Source: codewars | Difficulty: MEDIUM
Tags: Dynamic programming

Mathematics

Ad-hoc

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)]
	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
	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