Cho 1 số nguyên n (Với 1≤n≤10000). Tính số Fibonacci thứ n. Biết số Fibonacci - https://vi.wikipedia.org/wiki/Dãy_Fibonacci - là số mà số sau bằng tổng 2 số trước. Bắt đầu với số thứ 1 là 1 và số thứ 2 cũng là 1.

Lưu ý: Vì số đó có thể rất lớn nên sau khi tính xong lấy kết quả đó mod cho ~10^9~+7.

Ví dụ: số Fibonacci thứ 45 là : 1134903170. Sau khi mod nó (1134903170) cho ~10^9~+7 ta được số 134903163. Vậy đáp án là 134903163.

Input

Dòng đầu tiên có chứa 1 số nguyên n (Với 1≤n≤10000).

Output

Tính số Fibonacci thứ n sau khi đã mod cho ~10^9~+7.

Examples

Input

45

Output

134903163

Input

3

Output

2