2059. Стадион

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

По проекту, зрительские места на стадионе будет разбиты на несколько одинаковых секторов. Сектор представляет из себя нескольких рядов кресел по `m` кресел в каждом ряду с двумя проходами по бокам, так что к каждому месту можно будет пройти справа или слева. В каждом ряду кресла пронумерованы слева направо. Способом рассадки зрителей в одном ряду отдел называет перестановку чисел от единицы до `m`, соответствующую порядку, в котором зрители занимают свои места в этом ряду. Хорошим способом назовем такой способ, при котором никакому зрителю не придется проходить на пути к своему месту мимо уже сидящего человека. Вас же попросили посчитать, сколько существует различных таких способов. Считается, что очередной зритель начинает идти к своему месту только тогда, когда предыдущий за ним (если такой был) уже занял свое место.

В входном файле содержится одно целое число `m` (`1\ ≤\ m\ ≤\ 10^{18}`) – число мест в каждом ряду.

В выходной файл выведите одно число – число различных хороших способов рассадки зрителей по модулю `10^9\ +\ 7`.

1

1

3

4