Problem:

F: グリッドの番号

問題

えびちゃんは、横 n 列、縦 2 行のグリッドに 1 から 2 \times n までの整数をちょうど 1 つずつ書き込もうとしています。

グリッドの各マスにはちょうど 1 つの整数しか書き込めません。

普通に書き込むだけでは面白くないので、以下のようなルールを定めました。

隣り合う 2 つのマスに書き込まれた整数の、差の絶対値は k 以下である。

あるマスの右にマスが存在する時、あるマスに書き込まれた整数は、右のマスに書き込まれた整数より真に小さい。

あるマスの下にマスが存在する時、あるマスに書き込まれた整数は、下のマスに書き込まれた整数より真に小さい。

ここで、隣り合う 2 つのマスとは、あるマスと上下左右の辺を共有するマスのことを表します。

このような書き込み方は何通りあるでしょうか?
答えが非常に大きくなる可能性があるので、素数 m で割った余りを出力してください。

補足

上記の 2 番目のルールと 3 番目のルールは、以下の図のように、不等号に違反しないように整数を書き込むことを要求しています。

-->

入力形式

入力として整数が 3 つ与えられます。

n k m

制約

1 \leq n \leq 100

1 \leq k \leq 10

2 \leq m \leq 10^9+7

 m は素数

出力形式

数字の書き込み方の通り数を一行に出力してください。
また、末尾の改行を忘れないように注意してください。

入力例 1

3 2 7

出力例 1

1

-->

上記の書き込み方が条件を満たし、これ以外に条件を満たす書き込み方は存在しません。

入力例 2

5 10 11

出力例 2

9

m で割った余りを出力してください。



Sample input:
3 2 7


Sample output:
1

Submission status: Accepted

Solution code:
from collections import Counter
N, K, mod = map(int, input().split())
dp = [Counter() for _ in range(2*N)]

dp[0][(None, (0,))] = 1
for i in range(2*N-1):
    for (left, top), v in dp[i].items():
        if len(top) > K+1:
            continue
        if left == None:
            if top and i+1 - top[0] <= K:
                dp[i+1][(i+1, top)] = (dp[i+1][(i+1, top)] + v) % mod 
        elif (i+1 - left <= K) and len(top) > 1 and (i+1 - top[1] <= K):
            dp[i+1][(i+1, top[1:])] = (dp[i+1][(i+1, top[1:])] + v) % mod
        if top and (i+1 - top[-1] <= K):
            top = list(top)
            top.append(i+1)
            top = tuple(top)
            dp[i+1][(left, top)] = (dp[i+1][(left, top)] + v) % mod

res = 0
for (left, top), v in dp[2*N-1].items():
    if len(top) == 1:
        assert left == 2*N - 1
        res = (res + v) % mod
print(res)