ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2012, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Руины титанов: хитрые манипуляции

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
«Слушай, мне кажется, что создатели этого места были просто помешаны на экспериментах с монетами», — сказал Сорен войдя в очередную комнату. На этот раз его внимание привлекла большая платформа с кучей рычагов, на которой лежала одна маленькая монета. Альба ради интереса задействовал платформу, послав в неё слабый заряд магической энергии. Тут же на месте одной монеты появилось несколько таких же. Впрочем, вскоре они начали понемногу исчезать одна за другой, пока не осталась снова одна. Альба послал ещё один заряд, и монет снова стало несколько. Сразу же ещё один — и их количество уменьшилось.
Продолжая эксперименты, друзья выявили следующие закономерности:
  • Количество монет на платформе после подачи магического заряда зависит только от того, сколько их было на платформе до этого, и никак не зависит ни от силы заряда, ни от других факторов.
  • Количество монет от подачи заряда может как увеличиваться, так и уменьшаться или оставаться неизменным. При этом монет всегда не меньше одной и не больше n.
  • Через некоторое время после подачи заряда количество монет на платформе начинает постепенно убывать по одной до тех пор, пока не платформе не останется одна единственная монета. Причём происходит это достаточно медленно, чтобы при любом промежуточном количестве монет можно было успеть подать ещё один заряд.
  • Из платформы торчит n рычагов. Если сдвинуть i-й из них, то поменяется количество монет, которое получается, если послать заряд при i монетах на платформе. Причём, у рычага ровно n положений — по одному для каждого варианта получить от 1 до n монет.
Внимательно осмотрев платформу со всех сторон, Сорен обнаружил на ней небольшую потайную дверцу. Она явно была заперта и, скорее всего, отпиралась только при определённом положении всех рычагов. Подумав о том, что суммарное количество положений рычагов может быть слишком большое, друзья решили перебрать только те из них, при которых можно получить из одной монеты максимально возможные n монет. Таких должно быть явно меньше, но сколько именно?

Исходные данные

На входе дано единственное целое число n (2 ≤ n ≤ 5 000).

Результат

Выдайте единственное число — остаток от деления на 109 + 7 количества положений рычагов, которое предстоит перебрать Сорену и Альбе.

Пример

исходные данныерезультат
2
2
Автор задачи: Денис Дублённых
Источник задачи: NEERC 2012, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1918. Руины титанов: хитрые манипуляции