問題一覧 > 通常問題

No.1685 One by One

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 13
作問者 : Sumitacchan / テスター : 👑 hitonanode ygussany
お気に入りにしたユーザー ProblemId : 6821 / 自分の提出
問題文最終更新日: 2021-08-29 18:23:22
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 314 (順位表) の他の問題:

Problem Statement

There is a sequence $A=(A_1,A_2,\dots,A_N)$ of $N$ terms, and initially $A_i=0$ for all $i\ (1\le i\le N)$.

You will perform an operation consisting of the following series of steps exactly $M$ times.

  • Choose an integer $i\ (1\le i\le N)$.
  • Let $j=i+1$ or $j=i-1$. However, if $j=0$, replace it with $j=N$, and if $j=N+1$, replace it with $j=1$.
  • Increase the value of $A_i$ by $1$ and decrease the value of $A_j$ by $1$.

How many sequences $A$ are possible after the $M$ operations?
Since the answer can be very large, output it modulo $10^9+7$.

Input

$N\ \ M$

  • $2\le N\le 4000$
  • $0\le M\le 4000$
  • All input values are integers.

Output

Output the number of possible sequences $A$ after the $M$ operations, modulo $10^9+7$.

Sample

Sample 1
Input
3 1
Output
6

There are $6$ possibilities: $A=(1,-1,0),(-1,1,0),(0,1,-1),(0,-1,1),(1,0,-1),(-1,0,1)$.

Sample 2
Input
2 2
Output
3

There are $3$ possibilities: $A=(2,-2),(0,0),(-2,2)$.

Sample 3
Input
123 456
Output
317576076

Sample 4
Input
998 2443
Output
221398327

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