Ваше завдання порахувати кількість способів побудови суми ~n~, кидаючи кубик один або кілька разів. Кожен кидок дає результат від 1 до 6.

Наприклад, якщо ~n=3~, є 4 шляхи:

• 1+1+1
• 1+2
• 2+1
• 3

Обмеження

• ~1 \le n \le 10^6~

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

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

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

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

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

3

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

4