問題一覧 > 教育的問題

No.8048 Order and Harmony

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 25
作問者 : ミドリムシ
お気に入りにしたユーザー ProblemId : 2925 / 自分の提出
問題文最終更新日: 2019-04-01 20:51:31
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 April Fool Contest 2019 (順位表) の他の問題:

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
0
No sequence satisfies the conditions.

Sample 3
Input
100000
Output
149033233
Do not forget to take the result modulo $10^9+7$.

Sample 4
Input
114514810
Output
438430625

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