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

• ~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