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\le N\le 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