0512 - 剣剣波

問題

ほものくんは剣剣波が得意技です。
剣剣波とは物理技の「剣」と斬属性魔法の「波」とを繰り返す技です。
今、ほものくんは回数Nの新しい剣剣派を放とうと考えています。
美しくコンボを決めるために、次の2つの条件を守って剣検波を作らないといけません。

1. 「剣」は3回以上続いてはいけない
2. 「派」は「剣」のあとにしか置けない

ほものくんは何通りの剣剣派が放てるのか計算しようとしました。
しかし、INT0のデバフがかかっているので計算がうまくできません。

そこで、ほものくんの代わりに何通りの剣剣派が放てるかを求めてあげてください。
ただし、答えは非常に大きくなる可能性があるので10⁹+7で割った余りを出力してください。

入力

N

• 1行に長さN(1≦N≦10⁶)が与えられる。

出力

• 1行に10⁹+7で割った余りを出力する。 改行を忘れないこと。

入出力例

入力例1

3

出力例1

2

• 「剣剣波」と「剣派剣」の2通りがありえます。

入力例2

4

出力例2

3

• 「剣剣派剣」と「剣派剣派」と「剣派剣剣」の3通りがありえます。

入力例2

100

出力例2

831891005