Ваше завдання — підрахувати, якими способами отримати суму ~n~, кидаючи гральний кубик.

Кожен кидок дає ціле число від 1 … 6.

Наприклад, якщо ~n=10~, можливими способами є 3+3+4, 1+4+1+4 та 1+1+6+1+1.

Обмеження

• ~1≤n≤10^{18}~

Формат вхідних даних

Єдиний рядок вхідних даних містить ціле число ~n~.

Формат вихідних даних

Вивести кількість способів за модулем ~10^9+7~.

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

8

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

125