F - Permutation Oddness 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

{1,\ 2,\ ...,\ n} の順列 p = {p_1,\ p_2,\ ...,\ p_n} の「奇妙さ」を \sum_{i = 1}^n |i - p_i| と定義します。

奇妙さが k であるような {1,\ 2,\ ...,\ n} の順列の個数を 10^9+7 で割った余りを求めてください。

制約

  • 入力は全て整数である。
  • 1 \leq n \leq 50
  • 0 \leq k \leq n^2

入力

入力は以下の形式で標準入力から与えられる。

n k

出力

奇妙さが k であるような {1,\ 2,\ ...,\ n} の順列の個数を 10^9+7 で 割った余りを出力せよ。

入力例 1

3 2

出力例 1

2

{1,\ 2,\ 3} の順列は 6 個存在します。その中で奇妙さが 2 であるのは {2,\ 1,\ 3} と {1,\ 3,\ 2} の 2 つです。

入力例 2

39 14

出力例 2

74764168

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