Background

小左作为信息技术组的mengxin遇到了一道难题，于是他拿着难题去问dalao，dalao觉得这道太简单了，立马给出了答案，可是dalao又给了小左一道数学题，小左如果做不出来就不能再问dalao题目了，一向数学很差的小左没有办法，只好找你求助。

Description

计算 \(\Sigma_{K=0}^N\binom{N-K}{K} mod\;P\)
由于答案可能会很大，请将结果对P=1000000007取余。
其中\(\binom{N-K}{K}\)代表从N-K个物品中选k个物品的方案数。

Format

Input

输入一个正整数 N

Output

输出上面式子计算的结果

Sample

Input

2

Output

2

Limitation

30%的数据，n<=2000
70%的数据，n<=30000
100%的数据 , n < 2^63