У мальчика Кости очень много карточек с числами от \textbf{1} до \textbf{N}. В прошлый раз он выложил карточки от \textbf{1} до \textbf{N} по одной в возрастающем порядке и получил какое-то очень большое число. Сам он не смог придумать, что с ним можно сделать, но его папа, заметив разные свойства такого странно числа, предложил задачу на турнир очень похожий на тот, в котором участвуете вы. Прошло два года. И за это время много разных чисел было сложено из этих карточек. Однако Костя совсем не любит выкладывать монотонные последовательности из карточек, а все потому, что мама рассказала ему как много ребят расстроили из-за того, что не смогли решить первую задачу папы про карточки. Время идет, а задачи студентам все время хочется решать новые. Вот папа, собрав все мысли в кучу, решил, что в этот раз студенты будет решать следующую задачу: рассмотрим все возможные последовательности чисел длиной до \textbf{N} и элементами от \textbf{1} до \textbf{N}; выбросим из этого множества все монотонные последовательности (как вы помните про одну из них уже была задача два года назад); поставим в соответствие каждой последовательности одно число в\textbf{(N+1)}-ой системе счисления. Ну и что может быть проще --- найдем сумму этих чисел! Конечно, Костя еще маленький мальчик и вряд ли сможет решить эту задачу, но может вы сможете? \includegraphics{https://static.e-olymp.com/content/c3/c3aa6f15a35dc62eb732e3a907321201185a0320.jpg} Р.S. Последовательность \textbf{a_1}, \textbf{a_2}, ... , \textbf{a_k} преобразуется в число . \InputFile В единственной строке входного файла записано целое число \textbf{N} от \textbf{1} до \textbf{1000000000}. \OutputFile В единственной строке выходного файла выведите искомую сумма, но так как она может слишком огромной, то выведите только остаток от деления этого числа на \textbf{1000000007}. \textbf{Пояснение к примеру входных данных} При N = 3 возможны последовательности 1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33, 111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333, из которых не являются монотонными только 11, 22, 33, 111, 112, 113, 121, 122, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 322, 323, 331, 332, 333.