Числа Фібоначчі можна визначити таким чином:

• \(F_0 ​ =0\)
• \(F_1 ​ =1\)
• \(F_n ​ =F_{n−2}+F_{n−1}\) ​

Ваше завдання полягає в тому, щоб обчислити значення \(F_n\) ​ для заданого \(n\).

Вхідні дані

Єдиний рядок містить ціле число \(n\).

Вихідні дані

Вивести значення \(F_n\) ​ по модулю \(10^9+7\).

Обмеження

• \(0≤n≤10^{18}\)

Приклад вхідних даних

10

Приклад вихідних даних

55