Копатыч с Кар-Карычем переехали в посёлок Новогорный, где Копатыч занялся выводом сорта гигантских тыкв, а Кар-Карыч проводил дни, задумчиво наблюдая за горным пейзажем.

В один из дней Кар-Карыч предложил Копатычу насладиться горами вместе с ним. Для этого он предложил найти Копатычу количество новогорных перестановок чисел от $$$1$$$ до $$$n$$$. Перестановку Кар-Карыч называет новогорной в том и только в том случае, если её можно разбить на два непустых возрастающих подотрезка чисел. Например, перестановка $$$(2,5,1,3,4)$$$ будет новогорной, так как её можно разбить на два возрастающих подотрезка $$$(2,5)$$$ и $$$(1,3,4)$$$, а перестановка $$$(3,2,1)$$$ не будет новогорной. Кар-Карыч хочет, чтобы Копатыч как можно дольше думал о горах, поэтому даст ему несколько задач. Помогите Копатычу справиться с ними! Так как ответ на задачу может быть большим, выведите его остаток от деления на $$$10^9 + 7$$$.

Перестановка — это последовательность длины $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$, в которой все числа встречаются ровно по одному разу. Например, $$$(1)$$$, $$$(4, 3, 5, 1, 2)$$$, $$$(3, 2, 1)$$$ — перестановки, а $$$(1, 1)$$$, $$$(4, 3, 1)$$$, $$$(2, 3, 4)$$$ — нет.

Подотрезок — это непрерывная часть перестановки. Например, для перестановки $$$(2,3,1,5,4)$$$ $$$(2,3,1)$$$, $$$(1)$$$, $$$(5,4)$$$ будут являться подотрезками, а $$$(2,1,5)$$$ и $$$(4,5)$$$ — нет. Подотрезок является возрастающим, если числа в нём образуют возрастающую последовательность, то есть каждое число подотрезка, кроме первого, больше предыдущего. Подотрезки $$$(2,5,7)$$$ и $$$(3)$$$ являются возрастающими, а подотрезки $$$(2,1)$$$ и $$$(4,5,8,7)$$$ — нет.