На одной планете в далёкой галактике существует следующая легенда:

В начале времён демиург Ян Декс создал на самой высокой горе мира храм. В центре храма есть алтарь, на котором лежит куча из n драгоценных камней. Каждое утро два жреца — учитель и ученик — начинают делить эти камни, беря ненулевое количество камней из кучки по очереди. Учитель делает первый ход; при этом ученик ни в какой момент времени не может иметь больше камней, чем учитель. В итоге камни должны быть поделены поровну, а на алтаре не должно остаться ни одного камня.

В момент, когда жрецы не смогут выполнить задание или же в точности повторят все действия, сделанные при дележе в какой-то из предыдущих дней, злой дух-разрушитель Баг выйдет на свободу и разрушит планету.

По заданному количеству камней n вычислите максимально возможное время существования этого мира с момента начала времён и до пришествия Бага. Так как ответ может быть очень большим, выведите его остаток от деления на 10⁹ + 7.