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