题目内容

某数据分析模块需要将 $1$ 到 $n$ 的任务权值依次放置在 $n$ 个位置上。由于不同位置会被不同数量的连续区间覆盖，合理安排较大的权值可以提升最终的聚合结果。

给定一个整数 $n$，请构造一个长度为 $n$ 的排列 ${v_1,v_2,\dots,v_n}$。

对于该排列的每一个非空子数组，计算其中所有元素之和。将所有非空子数组对应的元素和再次相加，得到整个排列的区间聚合值。

你需要使这个区间聚合值尽可能大，并输出最大值以及任意一种能够达到最大值的排列。

排列：长度为 $n$ 的排列由 $1,2,\dots,n$ 这 $n$ 个整数组成，每个整数恰好出现一次。

子数组：从原数组中连续选取至少一个元素得到的数组称为子数组。

如果有多种排列均能达到最大区间聚合值，输出其中任意一种即可，系统会自动判断答案是否正确。由于答案不唯一，自测运行功能可能与示例输出不同，请自行确认结果是否合法。

输入描述

输入一行，一个整数 $n$（$1\le n\le 250000$）。

输出描述

第一行输出一个整数，表示最大区间聚合值对 $10^9+7$ 取模后的结果。

第二行输出 $n$ 个整数，表示你构造出的排列。

如果存在多种合法方案，输出任意一种即可。

样例1

输入

5

输出

116
2 4 5 3 1

说明

长度为 $5$ 时，从左到右的五个位置分别会被 $5,8,9,8,5$ 个非空子数组覆盖。

因此，该排列产生的区间聚合值为

较大的元素被安排在覆盖次数更多的位置，因此该排列能够取得最大值。

样例2

输入

2

输出

6
2 1

说明

排列 $2,1$ 的三个非空子数组分别为 $[2]$、$[1]$ 和 $[2,1]$，对应的元素和为 $2,1,3$。

所以区间聚合值为

样例3

输入

6

输出

220
2 4 6 5 3 1

说明

六个位置被非空子数组覆盖的次数依次为 $6,10,12,12,10,6$。

因此该排列的区间聚合值为

最大的两个元素被放在覆盖次数最多的中间位置，其余元素也按照覆盖次数的大小进行安排，因此可以达到最大区间聚合值。