/ 
Time Limit: 2 sec / Memory Limit: 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