問題一覧 > 通常問題

No.1685 One by One

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : SumitacchanSumitacchan / テスター : hitonanodehitonanode ygussanyygussany
7 ProblemId : 6821 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-29 18:23:22

問題文

$N$ 項の数列 $A=(A_1,A_2,\dots,A_N)$ があり、最初は全ての $i\ (1\le i\le N)$ に対して $A_i=0$ です。

あなたは、次の一連の手順からなる操作をちょうど $M$ 回行います。

  • 整数 $i\ (1\le i\le N)$ を選ぶ。
  • $j=i+1$ または $j=i-1$ とする。ただし、$j=0$ となった場合は $j=N$ に、$j=N+1$ となった場合は $j=1$ に置き換える。
  • $A_i$ の値を $1$ 増やし、$A_j$ の値を $1$ 減らす。

$M$ 回の操作後の数列 $A$ としてあり得るものは何通りあるでしょうか。
答えは非常に大きくなることがあるので $10^9+7$ で割った余りを出力してください。

入力

$N\ \ M$

  • $2\le N\le 4000$
  • $0\le M\le 4000$
  • 入力は全て整数である。

出力

$M$ 回の操作後の数列 $A$ としてあり得るものの数を $10^9+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
3 1
出力
6

$A=(1,-1,0),(-1,1,0),(0,1,-1),(0,-1,1),(1,0,-1),(-1,0,1)$ の $6$ 通りです。

サンプル2
入力
2 2
出力
3

$A=(2,-2),(0,0),(-2,2)$ の $3$ 通りです。

サンプル3
入力
123 456
出力
317576076

サンプル4
入力
998 2443
出力
221398327

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。