Ряд 8

Последовательность натуральных чисел a₁, a₂, ..., a_n удовлетворяет следующему условию:

$a_n=\sum \frac{(i+j+k)!}{i!\cdot j!\cdot k!}$

В сумме рассматриваются уникальные целые всевозможные тройки i, j, k ≥ 0 и i + j + 2∙k = n.

Определите a_n по модулю 10⁹ + 7.

Входные данные

Входной файл INPUT.TXT содержит натуральное число n (1 ≤ n ≤ 10⁶).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Пример

Пояснение

Во втором примере n = 2. Так как i + j + 2∙k = n, то можно составить следующие комбинации троек: {0, 0, 1}, {0, 2, 0}, {1, 1, 0}, {2, 0, 0}. Откуда получаем, что a₂ = 1 + 1 + 2 + 1 = 5.

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]