Problem D: IkaNumber

数直線上の整数座標に, ねこの Taro の家, にんじん, うさぎの Hanako の家がこの順に並んでいる. 点 $x$ にいるイカは, 一回のジャンプで $x + 1$ または $x + 2$ に移動することができる.

あなたは, イカが Taro の家から Hanako の家までにんじんの置かれている座標に止まらずに行く経路が何通りあるか求めようとしたが, Taro の家, にんじん, Hanako の家の座標を知らないので 求めることができなかった. そこで, 代わりに経路の数として考えられる数をすべて列挙することにした.

ある Taro の家, にんじん, Hanako の家の配置に対してイカの経路数となる整数をイカ数と呼ぶことにする. $K$ 番目に小さいイカ数 (1-indexed) を mod 1,000,000,007 で求めよ.

Constraints

• $K$ will be between 1 and 1,000,000,000,000,000,000, inclusive.

Input

入力はイカの形式で与えられる:

$K$

Output

$K$ 番目に小さいイカ数を 1,000,000,007 で割った余りを 1 行に出力せよ.

Sample Input 1

5

Sample Output 1

5

Sample Input 2

8

Sample Output 2

9