Сума послідовностей
У хлопчика Кості є багато карток з числами від 1 до N. Минулого разу він виклав картки від 1 до N у зростаючому порядку і отримав дуже велике число. Сам він не знав, що з ним робити, але його тато, помітивши різні властивості цього числа, запропонував задачу на турнір, подібний до того, в якому ви берете участь.
Минуло два роки. За цей час з цих карток було складено багато різних чисел. Однак Костя не любить викладати монотонні послідовності, адже мама розповіла йому, як багато хлопців засмутилися, не вирішивши першу задачу тата про картки.
Час іде, а студентам завжди хочеться вирішувати нові задачі. Тому тато, зібравши всі думки, вирішив, що цього разу студенти будуть вирішувати таку задачу: розглянемо всі можливі послідовності чисел довжиною до N з елементами від 1 до N; виключимо з цієї множини всі монотонні послідовності (як ви пам'ятаєте, про одну з них вже була задача два роки тому); поставимо у відповідність кожній послідовності одне число в (N+1)-ій системі числення. І що може бути простіше — знайдемо суму цих чисел! Звісно, Костя ще маленький хлопчик і навряд чи зможе вирішити цю задачу, але можливо ви зможете?
P.S. Послідовність a_1, a_2, ... , a_k перетворюється в число.
Вхідні дані
В єдиному рядку вхідного файлу записано ціле число N від 1 до 1000000000.
Вихідні дані
В єдиному рядку вихідного файлу виведіть шукану суму, але оскільки вона може бути занадто великою, то виведіть тільки залишок від ділення цього числа на 1000000007.
Пояснення до прикладу вхідних даних
При 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.