Bạn được cho 1 số nguyên ~N~, hãy in ra số fibonacci thứ ~N~. Vì kết quả có khả năng sẽ lớn nên chúng ta sẽ lấy chia dư cho ~10^{9}+7~

Dãy fibonacci là dãy có tính chất số đằng sau sẽ bằng tổng 2 số đứng trước đó. Dãy cơ bản là như sau: 1, 1, 2, 3, 5,.....

Input

• Dòng đầu tiên chứa số nguyên ~N (1 \leq N \leq 1000)~

Output

• Số fibonacci thứ ~N~ đã được chia dư cho ~10^{9}+7~

Sample input 1

3

Sample output 1

2

Sample input 2

746

Sample output 2

164015224