Для перестановки p чисел від 1 до n, визначимо f(p) наступним чином: для кожної пари чисел (i,j) з 1≤i≤j≤n, порахуємо пару (min,max), де min — найменше число серед чисел ai,ai+1,…,aj, а max — найбільше з них. Тоді f(p) рівна кількості різних пар серед всіх 2n(n+1) пар.
Наприклад розглянемо перестановку (1,3,2).
Для пари (1,1), (min,max)=(1,1)
Для пари (1,2), (min,max)=(1,3)
Для пари (1,3), (min,max)=(1,3)
Для пари (2,2), (min,max)=(3,3)
Для пари (2,3), (min,max)=(2,3)
Для пари (3,3), (min,max)=(2,2)
Всього 5 різних пар, тому f((1,3,2))=5.
Знайдіть суму f(p) по всім перестановкам p довжини n, за модулем 109+7.
Єдиний рядок вхідних даних містить єдине число n (1≤n≤2⋅105).
Виведіть суму f(p) по всім перестановкам p довжини n, за модулем 109+7.