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 sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import numpy as np

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

# ある線を、左にまたぐ数の集合、右にまたぐ数の集合など

MOD = 10 ** 9 + 7

dp = np.zeros((N+1,N*N+1), dtype = np.int64) # ある線をまたぐ（左右）個数、これまでの合計点、場合の数
dp[0,0] = 1
for n in range(1,N+1):
    prev = dp
    dp = np.zeros_like(prev)
    for m in range(N):
        dp[m,m:] += prev[m,:N*N+1-m] # その点を不動点にしてそのまま
        dp[m,m:] += prev[m,:N*N+1-m] * m # どれかをそこに留めてのこりを右に
        dp[m+1,m+1:] += (m+1) * prev[m,:N*N-m] # その点ごと全部右に。左に流す方をどれか残す
        dp[m,m:] += prev[m,:N*N+1-m] * m # xを左に、左から来たのは全て右に
        dp[m,m:] += (m+1) * prev[m+1,:N*N+1-m] # その点ごと全部右に。左に流す方をどれか残す
    dp %= MOD

if K&1:
    answer = 0
else:
    answer = dp[0,K//2]

print(answer)