Ваше завдання — підрахувати, якими способами отримати суму \(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