問題一覧 > 通常問題

No.314 ケンケンパ

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 594
作問者 : roiti46
お気に入りにしたユーザー ProblemId : 882 / 自分の提出
問題文最終更新日: 2026-06-25 03:34:10
Ken-Ken-Pa
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. Show the original
Advent Calendar Contest 2015 (順位表) の他の問題:

Note

This problem was created as the problem for day 7 of Advent Calendar Contest Advent Calendar 2015.

Problem Statement

Taro likes Ken-Ken-Pa.
Ken-Ken-Pa is a game in which you repeat "Ken", a hop on one foot, and "Pa", a landing on both feet.
Taro is now thinking of making a new Ken-Ken-Pa course of length N.
To make the Ken-Ken-Pa course fun, he must follow the two conditions below when making the course.

1. "Ken" must not continue 3 or more times in a row
2. "Pa" can be placed only right after "Ken"

Taro wonders how many courses he can make, but he is a kindergartener and cannot calculate well.
So, please find the number of courses that can be made on his behalf.
Since the answer can be very large, output the remainder when divided by 109+7.

Input

$N$

N is an integer between 1 and 106, inclusive.

Output

Output the number of courses that can be made, modulo 109+7.

Sample

Sample 1
Input
3
Output
2

There are 2 possibilities: "Ken Ken Pa" and "Ken Pa Ken".

Sample 2
Input
4
Output
3

There are 3 possibilities: "Ken Ken Pa Ken", "Ken Pa Ken Pa", and "Ken Pa Ken Ken".

Sample 3
Input
100
Output
831891005

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