«Слушай, мне кажется, что создатели этого места были просто помешаны на экспериментах с монетами», — сказал Сорен войдя в очередную комнату. На этот раз его внимание привлекла большая платформа с кучей рычагов, на которой лежала одна маленькая монета. Альба ради интереса задействовал платформу, послав в неё слабый заряд магической энергии. Тут же на месте одной монеты появилось несколько таких же. Впрочем, вскоре они начали понемногу исчезать одна за другой, пока не осталась снова одна. Альба послал ещё один заряд, и монет снова стало несколько. Сразу же ещё один — и их количество уменьшилось.

Продолжая эксперименты, друзья выявили следующие закономерности:

Внимательно осмотрев платформу со всех сторон, Сорен обнаружил на ней небольшую потайную дверцу. Она явно была заперта и, скорее всего, отпиралась только при определённом положении всех рычагов. Подумав о том, что суммарное количество положений рычагов может быть слишком большое, друзья решили перебрать только те из них, при которых можно получить из одной монеты максимально возможные n монет. Таких должно быть явно меньше, но сколько именно?

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

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