Problem:


Score : 600 points

Problem Statement

Let us define the oddness of a permutation p = {p_1,\ p_2,\ ...,\ p_n} of {1,\ 2,\ ...,\ n} as \sum_{i = 1}^n |i - p_i|.

Find the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

Constraints

All values in input are integers.

1 \leq n \leq 50

0 \leq k \leq n^2

Input

Input is given from Standard Input in the following format:

n k

Output

Print the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

Sample Input 1

3 2

Sample Output 1

2

There are six permutations of {1,\ 2,\ 3}. Among them, two have oddness of 2:  {2,\ 1,\ 3} and {1,\ 3,\ 2}.

Sample Input 2

39 14

Sample Output 2

74764168



Sample input:
3 2


Sample output:
2

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int, input().split())
m = n**2
mod = 10**9+7
dp = np.zeros((n+1, n+1, m+1), dtype=np.int64)
dp[0,0,0] = 1
for i in range(1, n+1):
  for j in range(i+1):
    dp[i,j,2*j:] = (2*j+1)*dp[i-1,j,:m+1-2*j]
    if j+1 <= i-1:
      dp[i,j,2*j:] += (j+1)*(j+1)*dp[i-1,j+1,:m+1-2*j]
    if j:
      dp[i,j,2*j:] += dp[i-1,j-1,:m+1-2*j]
    dp[i,j,2*j:] %= mod
ans = dp[n,0,k]
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
MOD = 10**9+7

# dp[i][j][k]:
# ウサギ1~i, カメ1~i (うちj個は相手が未定)まで見ていて，
# 確定している奇妙さがkであるような場合の数
dp = []
for _ in range(55):
    dp.append([[0] * (55*55) for _ in range(55)])

dp[0][0][0] = 1

for i in range(N+1):
    for j in range(N+1):
        for k in range(N*N+1):
            if k-2*j < 0 or i-1 < 0: continue

            dp[i][j][k] += (2*j+1) * dp[i-1][j][k-2*j] % MOD
            dp[i][j][k] %= MOD

            dp[i][j][k] += (j+1)*(j+1) * dp[i-1][j+1][k-2*j] % MOD
            dp[i][j][k] %= MOD

            if j > 0:
                dp[i][j][k] += dp[i-1][j-1][k-2*j]
                dp[i][j][k] %= MOD
            
print(dp[N][0][K])

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/abc134/tasks/abc134_f

少ないのは何？
一応マッチングの問題といえる

dp？
数字 >= index の位置と、数字 < index の場合がある。
前の場合の数字の和を An
indexの和をAi
後者を Bn / Biとする

(An-Ai) + (Bi-Bn) = k となるようにすればいい


箱根的に左から見ていく場合を考える。
そこのindexと、そこに置いてあった数字をどうするか考える

●そこのindex
    取っておいた数字を置く→数字 < indexとなるので Biに加算 (正の寄与)
        →とっておいた数字が1以上ないとダメ
    開けておく　→ Aiに加算 (負の寄与)・後で埋めないとダメ

●そこの数字
    左の空いてるところに入れる　→　Anに加算 (正の寄与)・空きがないとダメ
    取っておく　→ Bnに加算 (負の寄与)

dp[i][score][x][y] = i番目まで見て左に空きマスがx個あり、y個数字を取ってある場合の場合の数
dp[n][score][0][0] が答え
空きマスの数ととってある数字の個数は同じなので添え字を減らせる

→ dp[i][score][x] = i番目まで見て左に空きマスがx個あり、x個数字を取ってある場合の場合の数
dp[n][k][0] が答え
scoreの取りうる範囲は -n**2 ～ n**2でいいよね

"""

n,k = map(int,input().split())

scr = 10000

dp = [[[0] * (n+1) for i in range(scr)] for j in range(n+1)]
dp[0][0][0] = 1
mod = 10**9+7

for i in range(0,n):
    for nsc in range(-scr//2,scr//2):
        for x in range(n):

            #今見ている数字はi+1で求められる
            nownum = i+1

            #何もしない場合
            dp[i+1][nsc][x] += dp[i][nsc][x]
            dp[i+1][nsc][x] %= mod

            #数字を←に置き、取っておいた数字を置く場合
            #どちらも正の寄与なので +2nownum
            #xは1減る
            if x > 0:
                dp[i+1][(nsc+2*nownum)%scr][x-1] += dp[i][nsc][x] * x * x
                dp[i+1][(nsc+2*nownum)%scr][x-1] %= mod

            #数字を左に置き、マスを空ける場合
            #寄与は0
            #xは変わらず
            if x > 0:
                dp[i+1][nsc][x] += dp[i][nsc][x] * x
                dp[i+1][nsc][x] %= mod

            #数字をとっておき、マスに入れる場合
            #寄与は0
            #xは変わらず
            if x > 0:
                dp[i+1][nsc][x] += dp[i][nsc][x] * x
                dp[i+1][nsc][x] %= mod

            #数字をとっておき、マスもとっておく場合
            #どちらも負の寄与
            #xは1ふえる
            if x < n:
                dp[i+1][(nsc-2*nownum)%scr][x+1] += dp[i][nsc][x]
                dp[i+1][(nsc-2*nownum)%scr][x+1] %= mod

print (dp[n][k][0] % mod)

Submission status: Accepted

Solution code:
MOD=10**9+7
n,kk=map(int,input().split())

dp=[[[0]*(n**2+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=1

for i in range(1,n+1):
  for j in range(i+1):
    for k in range(n**2+1):
      if k-2*j<0:
        continue
      dp[i][j][k]=(2*j+1)*dp[i-1][j][k-2*j]  
      if j+1<=n:
        dp[i][j][k]+=(j+1)**2*dp[i-1][j+1][k-2*j]
      if j-1>=0:
        dp[i][j][k]+=dp[i-1][j-1][k-2*j]
      dp[i][j][k]%=MOD
      
print(dp[n][0][kk])

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
MOD = 10**9+7
n, K = map(int, input().split())
dp = [[[0 for _ in range(K+1)] for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1

for i in range(1, n+1):
	for j in range(n+1):
		for k in range(K+1):
			if k >= 2*j:
				dp[i][j][k] += (2*j+1) * dp[i-1][j][k-2*j]
			if k >= 2*j and j < n:
				dp[i][j][k] += (j+1) * (j+1) * dp[i-1][j+1][k-2*j]
			if k >= 2*j and j > 0:
				dp[i][j][k] += dp[i-1][j-1][k-2*j]
			dp[i][j][k] %= MOD

print(dp[n][0][K])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, K = read_values()
    dp = [
        [[0 for i in range(N ** 2 + 1)] for ii in range(N + 1)] for iii in range(N + 1)
    ]
    dp[0][0][0] = 1

    for i in range(1, N + 1):
        for j in range(N + 1):
            for k in range(K + 1):
                if k - 2 * j < 0:
                    continue

                dp[i][j][k] = (
                    (2 * j + 1) * dp[i - 1][j][k - 2 * j]
                    + (
                        (j + 1) * (j + 1) * dp[i - 1][j + 1][k - 2 * j]
                        if j + 1 <= N
                        else 0
                    )
                    + dp[i - 1][j - 1][k - 2 * j]
                ) % mod

    print(dp[N][0][K])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
n,m=map(int,input().split())
a=[[0 for _ in range(m+3)] for _ in range(n+2)]
a[0][0]=1
a[1][2]=1
for i in range(1,n):
  b=copy.deepcopy(a)
  for j in range(0,i+2):
    for k in range(0,m+1):
      if k>=2*j:
        a[j][k]=(2*j+1)*b[j][k-2*j]+(j+1)**2*b[j+1][k-2*j]
        if j>0:
          a[j][k]+=b[j-1][k-2*j]
        a[j][k]%=(10**9+7)
      else:
        a[j][k]=0
print(a[0][m])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    mod = 1000000007
    N, K = map(int, input().split())
    n = N//2
    dp = [[[0] * (N**2+1) for _ in range(n+1)] for _ in range(N+1)]
    dp[0][0][0] = 1

    for i in range(N):
        for j in range(n+1):
            for k in range(N**2+1):
                #print(i+1, j, k+2*j)
                if k+2*j <= N**2:
                    dp[i+1][j][k+2*j] = (dp[i+1][j][k+2*j] + dp[i][j][k])%mod
                    if j+1 <= n:
                        dp[i+1][j+1][k+2*j] = (dp[i+1][j+1][k+2*j] + dp[i][j][k])%mod
                    dp[i + 1][j][k + 2 * j] = (dp[i + 1][j][k + 2 * j] + (dp[i][j][k]*2 * j)%mod) % mod
                    dp[i+1][j-1][k+2*j] = (dp[i+1][j-1][k+2*j] + (dp[i][j][k]*j*j)%mod)%mod
    print(dp[-1][0][K])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N, K = map(int, input().split())

dp = [[[0 for _ in range(2610)] for _ in range(51)] for _ in range(51)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(K + 1):
            dp[i + 1][j + 1][k + 2 * j + 2] += dp[i][j][k]
            if j > 0:
                dp[i + 1][j][k + 2 * j] += dp[i][j][k] * j
                dp[i + 1][j][k + 2 * j] += dp[i][j][k] * j

            dp[i + 1][j][k + 2 * j] += dp[i][j][k]

            if j > 0:
                dp[i + 1][j - 1][k + 2 * j - 2] += dp[i][j][k] * j * j


print(dp[N][0][K] % mod)

Submission status: Accepted

Solution code:
def permutation_oddness(n: int, k: int)->int:
    MOD = 10**9 + 7
    MAX_K = n*n//2

    if k > MAX_K or k % 2 == 1:
        return 0

    dp = [[[0] * (MAX_K+1) for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0][0] = 1
    for i in range(n):
        for j in range(n+1):
            for odd in range(0, MAX_K+1, 2):
                if odd < 2*j:
                    continue

                dp[i+1][j][odd] = (2*j+1) * dp[i][j][odd-2*j] % MOD
                if j+1 <= n:
                    dp[i+1][j][odd] += (j+1)*(j+1)*dp[i][j+1][odd-2*j] % MOD
                if j-1 >= 0:
                    dp[i+1][j][odd] += dp[i][j-1][odd-2*j] % MOD
                dp[i+1][j][odd] %= MOD

    return dp[n][0][k]


if __name__ == "__main__":
    n, k = map(int, input().split())
    ans = permutation_oddness(n, k)
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,K=map(int,input().split())
    dp=[[[0]*2700 for _ in range(55)] for _ in range(55)]
    dp[0][0][0]=1
    for i in range(n):
        for j in range(i+1):
            for k in range(K+1):
                dp[i+1][j][k+2*j]+=dp[i][j][k]*(2*j+1)
                dp[i+1][j][k+2*j]%=MOD
                dp[i+1][j+1][k+2*(j+1)]+=dp[i][j][k]
                dp[i+1][j+1][k+2*(j+1)]%=MOD
                if(j):
                    dp[i+1][j-1][k+2*(j-1)]+=dp[i][j][k]*j*j
                    dp[i+1][j-1][k+2*(j-1)]%=MOD
    print(dp[n][0][K])
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,K=map(int,input().split())
    dp=[[[0]*2700 for _ in range(55)] for _ in range(55)]
    dp[0][0][0]=1
    for i in range(n):
        for j in range(i+1):
            for k in range(K+1):
                dp[i+1][j][k+2*j]+=(2*j+1)*dp[i][j][k]
                dp[i+1][j][k+2*j]%=MOD
                dp[i+1][j+1][k+2*(j+1)]+=dp[i][j][k]
                dp[i+1][j+1][k+2*(j+1)]%=MOD
                if(j):
                    dp[i+1][j-1][k+2*(j-1)]+=j*j*dp[i][j][k]
                    dp[i+1][j-1][k+2*(j-1)]%=MOD
    print(dp[n][0][K])
resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
dp = [[[0]*(k+2*(n+1)) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(i+1):
        for l in range(k+1):
            dp[i+1][j+1][l+2*(j+1)] += dp[i][j][l]
            dp[i+1][j+1][l+2*(j+1)]%=mod
            dp[i+1][j][l+2*j] += dp[i][j][l]*(j*2+1)
            dp[i+1][j][l+2 * j] %= mod
            if j!= 0:
                dp[i+1][j-1][l+(j-1)*2] += dp[i][j][l]*j*j
                dp[i+1][j-1][l+(j-1)*2]%=mod



print(dp[n][0][k]%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
dp = [[[0]*n**2*4 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(i+1):
        for l in range(k+1):
            dp[i+1][j+1][l+2*(j+1)] += dp[i][j][l]
            dp[i+1][j+1][l+2*(j+1)]%=mod
            dp[i+1][j][l+2*j] += dp[i][j][l]*(j*2+1)
            dp[i+1][j][l+2 * j] %= mod
            if j!= 0:
                dp[i+1][j-1][l+(j-1)*2] += dp[i][j][l]*j*j
                dp[i+1][j-1][l+(j-1)*2]%=mod



print(dp[n][0][k]%mod)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10**9 + 7

N,K = map(int,read().split())

# 左からの流入量、コスト
L = N*(N-1)//2+1
dp = np.zeros((N,L),dtype=np.int64)
dp[0,0] = 1

for _ in range(1,N+1):
    prev = dp
    dp = np.zeros_like(prev)
    for n in range(N):
        x = prev[n]
        # どれかを不動点に残りを等個数だけ左右に流す
        dp[n,n:] += x[:L-n] * (n+n+1)
        # 左からのものを採用、自身は左に流す
        if n > 0: dp[n-1,n-1:] += x[:L-n+1] * n
        # 右からのものを採用、自身は右に流す
        if n+1 < N: dp[n+1,n+1:] += x[:L-n-1] * (n+1)
    dp %= MOD

x = dp[0]
if K&1:
    answer = 0
elif K//2 < L:
    answer = x[K//2]
else:
    answer = 0
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10**9 + 7

N,K = map(int,read().split())

# 左からの流入量、コスト
L = N*(N-1)//2+1
dp = np.zeros((N,L),dtype=np.int64)
dp[0,0] = 1

for _ in range(1,N+1):
    prev = dp
    dp = np.zeros_like(prev)
    for n in range(N):
        # 自身を不動点にしてそのまま左右に流す
        dp[n,n:] += prev[n,:L-n]
        # 左からのものを採用、自身は左に流す
        if n > 0: dp[n-1,n-1:] += prev[n,:L-n+1] * n
        # 左からのものを採用、自身は右に流す
        dp[n,n:] += prev[n,:L-n] * n
        # 右からのものを採用、自身は左に流す
        dp[n,n:] += prev[n,:L-n] * n
        # 右からのものを採用、自身は右に流す
        if n+1 < N: dp[n+1,n+1:] += prev[n,:L-n-1] * (n+1)
    dp %= MOD

x = dp[0]
if K&1:
    answer = 0
elif K//2 < L:
    answer = x[K//2]
else:
    answer = 0
print(answer)

Submission status: Accepted

Solution code:
n, K = map(int, input().split())
dp = [[0]*(n**2+1) for _ in range(n+2)]
dp[0][0] = 1
for i in range(n):
    ndp = [[0]*(n**2+1) for _ in range(n+2)]
    for j in range(i+2):
        for k in range(n**2+1):
            if k-2*j<0:
                continue
            ndp[j][k] = ((2*j+1)*dp[j][k-2*j]+(j+1)*(j+1)*dp[j+1][k-2*j]+dp[j-1][k-2*j])%(10**9+7)
    dp = ndp
print(dp[0][K])

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))

# # A: {1, 2, ..., N}
# # B: 作る数列
# # dp[i, k, a, b]:
# # i まで見て
# # 奇妙さが k で
# # A のうち場所が決まってない数が a
# # B のうち入れる A が決まってない数が b
# dp = np.zeros((N + 1, K + 1, N + 1, N + 1), dtype=int)
# dp[0, 0, 0, 0] = 1
# for i in range(N):
#     for k in range(K + 1):
#         for a in range(N + 1):
#             for b in range(N + 1):
#                 # A[i] を B[i] に持ってく
#                 if k + a + b <= K:
#                     dp[i + 1][k + a + b][a][b] += dp[i][k][a][b]
#                 # 場所が決まってない A を B[i] に入れる
#                 # 場所が決まってない B に A[i] を入れる
#                 if a > 0 and b > 0 and k + a + b - 2 <= K:
#                     dp[i + 1][k + a + b - 2][a - 1][b - 1] += dp[i][k][a][b] * a * b
#                 # 片方だけ決める
#                 if a > 0 and b > 0 and k + a + b <= K:
#                     dp[i + 1][k + a + b][a][b] += dp[i][k][a][b] * a
#                     dp[i + 1][k + a + b][a][b] += dp[i][k][a][b] * b
#                 # 両方決めない
#                 if k + a + b + 2 <= K and a + 1 < N and b + 1 < N:
#                     dp[i + 1][k + a + b + 2][a + 1][b + 1] += dp[i][k][a][b]
# print(dp[-1][K][0][0] % MOD)


# # a と b は常に同じなのでまとめる
# dp = np.zeros((N + 1, K + 1, N + 1), dtype=int)
# dp[0, 0, 0] = 1
# for i in range(N):
#     for k in range(K + 1):
#         for a in range(N + 1):
#             # A[i] を B[i] に持ってく
#             if k + a * 2 <= K:
#                 dp[i + 1][k + a * 2][a] += dp[i][k][a]
#             # 場所が決まってない A を B[i] に入れる
#             # 場所が決まってない B に A[i] を入れる
#             if a > 0 and k + a * 2 - 2 <= K:
#                 dp[i + 1][k + a * 2 - 2][a - 1] += dp[i][k][a] * (a ** 2)
#             # 片方だけ決める
#             if a > 0 and k + a * 2 <= K:
#                 dp[i + 1][k + a * 2][a] += dp[i][k][a] * a * 2
#             # 両方決めない
#             if k + a * 2 + 2 <= K and a + 1 < N:
#                 dp[i + 1][k + a * 2 + 2][a + 1] += dp[i][k][a]
#     dp[i + 1] %= MOD
# print(dp[-1][K][0] % MOD)

# a と b は常に同じなのでまとめる
dp = np.zeros((N + 1, K + 1, N + 1), dtype=int)
dp[0, 0, 0] = 1
for i in range(N):
    for a in range(N + 1):
        k = np.arange(K + 1)
        # A[i] を B[i] に持ってく
        if a == 0:
            dp[i + 1, :, a] += dp[i, :, a]
        else:
            dp[i + 1, a * 2:, a] += dp[i, :-(a * 2), a]

        # 場所が決まってない A を B[i] に入れる
        # 場所が決まってない B に A[i] を入れる
        if a * 2 - 2 == 0:
            dp[i + 1, :, a - 1] += dp[i, :, a] * (a ** 2)
        elif a * 2 - 2 > 0:
            dp[i + 1, a * 2 - 2:, a - 1] += dp[i, :-(a * 2 - 2), a] * (a ** 2)

        # 片方だけ決める
        if a > 0:
            dp[i + 1, a * 2:, a] += dp[i, :-(a * 2), a] * a * 2

        # 両方決めない
        if a + 1 < N:
            dp[i + 1, a * 2 + 2:, a + 1] += dp[i, :-(a * 2 + 2), a]
    dp[i + 1] %= MOD
print(dp[-1][K][0] % MOD)

# ans = 0
# for li in itertools.permutations(range(N)):
#     ans += abs(np.array(li) - np.arange(N)).sum() == K
#     if abs(np.array(li) - np.arange(N)).sum() == K:
#         print(np.array(li) + 1)
# print(ans)

Submission status: Accepted

Solution code:
import numpy as np


def solve(n, k):
    if k % 2 == 1:
        return 0
    k //= 2

    MOD = 10 ** 9 + 7

    dp = np.zeros((1, k + 1), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(1, n + 1):
        max_d = min(i + 1, n - i + 1, k + 1)
        ndp = np.zeros((max_d, k + 1), dtype=np.int64)
        for d, ks in enumerate(dp):
            base = ks[:k - d + 1]
            if d > 0:
                ndp[d - 1, d:] += base * d ** 2
            if max_d > d:
                ndp[d, d:] += base * (2 * d + 1)
            if max_d > d + 1:
                ndp[d + 1, d:] += base
        dp = ndp % MOD

    return dp[0, k]


n, k = map(int, input().split())
print(solve(n, k))