問題一覧 > 教育的問題

No.3048 Order and Harmony

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 21
作問者 : ミドリムシ+ミドリムシ+
0 ProblemId : 2925 / 出題時の順位表
問題文最終更新日: 2019-04-01 20:51:31

問題文

以下では、列 $X$ と整数 $s, t\ (s<t)$ について、列 $X_s, X_{s+1}, ... X_{t-1}$ (0-indexed) を $X[s, t)$ と表す。ただし、$X_{|X|+m}=X_m$ とする。
また、ある列の総和が $0$ であるとき、その列は 令和 であるとする。
また、令和である列 $X[s, t)\ (s<t)$ が only one であるとは、$s<x<t$ を満たすどの整数 $x$ についても $X[s, x)$ が令和でないことを指す。

次の条件を全て満たす整数列 $A$ の個数を $10^9+7$ で割った余りを求めなさい。
・$A$ の全ての要素は $-1$ または $1$ である。
・$A$ は令和である。
・$0≦l<|A|$ と $l<r$ を満たす整数 $l, r$ の組で $A[l, r)$ が only one なものはちょうど $K$ 個ある。

入力

$K$

・入力は全て整数である。
・$1≦K≦10^9$

出力

答えを出力し、最後に改行してください。

サンプル

サンプル1
入力
4
出力
6

例えば、$A={1, -1, 1, -1}$ とすると、$A[0, 2), A[1, 3), A[2, 4), A[3, 5)$ が only one となる。

サンプル2
入力
3
出力
0
条件を満たす列は存在しない。

サンプル3
入力
100000
出力
149033233
$10^9+7$ で割るのを忘れずに。

サンプル4
入力
114514810
出力
438430625

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