No.770 Median Sequence
PulmnThis 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. Show the original
Problem Statement
Find the number of integer sequences $A$ of length $N$ that satisfy the following condition. Since this value can be very large, output the remainder when divided by $10^9+7$.
Condition: There exists an integer sequence $B$ of length $N$, with each element between $1$ and $N$ inclusive, that satisfies the following equations. Here, $med(x,y,z)$ denotes the median of the $3$ values $\{x,y,z\}$.
$A_1=med(1,B_1,N)$
$A_2=med(med(1,B_1,N-1),B_2,N)$
$A_3=med(med(med(1,B_1,N-2),B_2,N-1),B_3,N)$
$\vdots$
$A_i=med(med(med(\dots med(\dots med(med(1,B_1,N-i+1),B_2,N-i+2),\dots ,B_j,N-i+j)\dots ),B_{i-1},N-1),B_i,N)$
$\vdots$
$A_N=med(med(med(\dots med(\dots med(med(1,B_1,1),B_2,2),\dots ,B_j,j)\dots ),B_{N-1},N-1),B_N,N)$
* Please refer to the samples.
Input
$N$
$1\le N\le 3,000$
Output
Output the number of integer sequences $A$ satisfying the condition, modulo $10^9+7$. Print a newline at the end.
Sample
Sample 1
Input
6
Output
1448
For example, $A=(1,2,6,5,4,6)$ satisfies the condition, since taking $B=(1,2,6,3,1,6)$ satisfies the following equations.
$A_1=med(1,B_1,6)$
$A_2=med(med(1,B_1,5),B_2,6)$
$A_3=med(med(med(1,B_1,4),B_2,5),B_3,6)$
$A_4=med(med(med(med(1,B_1,3),B_2,4),B_3,5),B_4,6)$
$A_5=med(med(med(med(med(1,B_1,2),B_2,3),B_3,4),B_4,5),B_5,6)$
$A_6=med(med(med(med(med(med(1,B_1,1),B_2,2),B_3,3),B_4,4),B_5,5),B_6,6)$
Sample 2
Input
1
Output
1
Sample 3
Input
100
Output
328638438
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。