Делегации на школьную MUN

В школе готовятся к Model United Nations. Нужно разбить класс на делегации так, чтобы в каждой делегации было ровно 2 или ровно 3 ученика. Все ученики различимы (у каждого своё имя), а порядок делегаций не важен.

Посчитайте, сколькими способами можно сделать такое разбиение.

Так как ответ может быть очень большим, выведите его по модулю 1\,000\,000\,007.

Формат ввода Одно целое число n — количество учеников в классе.

Формат вывода Одно число — количество способов разбить n учеников на делегации размеров 2 и 3 по модулю 1\,000\,000\,007.

Ограничения

• 2 ≤ n ≤ 200000

Пример Ввод:

4

Вывод:

3