No.1685 One by One
タグ : / 解いたユーザー数 13
作問者 :
Sumitacchan
/ テスター :
👑
hitonanode
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もしくは右上の雲マークをクリックしてアカウントを作成してください。