No.8048 Order and Harmony
タグ : / 解いたユーザー数 25
作問者 :
Problem Statement
Below, for a sequence $X$ and integers $s, t\ (s<t)$, the sequence $X_s, X_{s+1}, ... X_{t-1}$ (0-indexed) is denoted by $X[s, t)$, where $X_{|X|+m}=X_m$.
Also, a sequence is said to be Reiwa if its sum is $0$.
Also, a Reiwa sequence $X[s, t)\ (s<t)$ is said to be only one if $X[s, x)$ is not Reiwa for every integer $x$ satisfying $s<x<t$.
Find the number, modulo $10^9+7$, of integer sequences $A$ satisfying all of the following conditions.
・Every element of $A$ is $-1$ or $1$.
・$A$ is Reiwa.
・There are exactly $K$ pairs of integers $l, r$ satisfying $0≦l<|A|$ and $l<r$ such that $A[l, r)$ is only one.
Input
$K$
・All inputs are integers.
・$1≦K≦10^9$
Output
Output the answer, followed by a newline.
Sample
Sample 1
Input
4
Output
6
For example, if $A={1, -1, 1, -1}$, then $A[0, 2), A[1, 3), A[2, 4), A[3, 5)$ are only one.
Sample 2
Input
3
Output
0No sequence satisfies the conditions.
Sample 3
Input
100000
Output
149033233Do not forget to take the result modulo $10^9+7$.
Sample 4
Input
114514810
Output
438430625
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。