配点: $900$ 点

問題文

以下の条件をともに満たす長さ $2N$ の数列 $A = (A_1, A_2, \dots, A_{2N})$ は、何種類あるでしょうか？

• 数列 $A$ は、$N$ 個の $+1$ と $N$ 個の $-1$ で構成される。
• $A_l + A_{l+1} + \cdots + A_r = 0$ となる $l, r$ の組み合わせ $(1 \leq l \leq r \leq 2N)$ はちょうど $K$ 個ある。

制約

• $1 \leq N \leq 30$
• $1 \leq K \leq N^2$
• 入力はすべて整数

入力

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

$N$ $K$

出力

問題文中の条件を満たす数列が何種類あるかを出力してください。 ただし、答えは必ず $64$ ビット符号付き整数型の範囲に収まります。

1 1

2

$N = 1, K = 1$ のとき、条件を満たす数列は次の $2$ 種類です。

• $A = (+1, -1)$
• $A = (-1, +1)$

2 3

2

$N = 2, K = 3$ のとき、条件を満たす数列は次の $2$ 種類です。

• $A = (+1, -1, -1, +1)$
• $A = (-1, +1, +1, -1)$

3 7

6

$N = 3, K = 7$ のとき、条件を満たす数列は次の $6$ 種類です。

• $A = (+1, -1, +1, -1, -1, +1)$
• $A = (+1, -1, -1, +1, +1, -1)$
• $A = (+1, -1, -1, +1, -1, +1)$
• $A = (-1, +1, +1, -1, +1, -1)$
• $A = (-1, +1, +1, -1, -1, +1)$
• $A = (-1, +1, -1, +1, +1, -1)$

8 24

568

$N = 8, K = 24$ のとき、条件を満たす数列は $568$ 種類あります。

30 230

761128315856702

$N = 30, K = 230$ のとき、条件を満たす数列は $761128315856702$ 種類あります。

25 455

0

$N = 25, K = 455$ のとき、条件を満たす数列はありません。