Xét dãy số Fibonaci {Fn} theo định nghĩa:

F1= F2= 1

Fn= Fn - 1+ Fn - 2 với mọi n > 2

Cho n, hãy tính Fn và đưa ra số dư của Fn chia cho (~ 10^6 ~+ 7)

Input

n (0 < n ≤ ~ 10^6 ~)

Output

một số nguyên – số dư tìm được.

Sample

Input #1

1

Output #1

1

Input #2

11

Output #2

89

Input #3

121

Output #3

146484

Problem source: NTUCoder.net