该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem F. Form a Larger Knapsack

Input file:　standard input
Output file:　standard output
Time limit:　1 second
Memory limit:　256 megabytes
Judgement protocol:　Special Judge

黄神有 $n$ 个背包，大小分别是从 $1$ 到 $n$。

现在黄神要将这 $n$ 个背包合成一个大背包。

首先黄神将这 $n$ 个背包排成一行。

每一轮合成，从相邻的两个背包得到一个新的背包，大小为两个背包的大小之和，旧背包消失。

合成 $n−1$ 轮，得到一个大背包。

例如：

初始有 $4$ 个背包，顺序为 $[1,4,3,2]$。

第一轮：$[5,7,5]$。

第二轮：$[12,12]$。

第三轮：$[24]$。

$4$ 个背包得到一个大小为 $24$ 的背包。

现在黄神想知道他的 $n$ 个背包，初始的顺序是什么，才能获得最大的背包？

Input

输入包含一行一个整数 $n$ $(1 \leq n \leq 10 ^ 3)$。

Output

第一行输出一个非负整数，表示最终的背包大小。

第二行输出 $n$ 个整数，表示初始 $n$ 个背包的顺序。

对于背包的大小，答案可能太大，请对 $10^9+7$ 取模再输出。

背包的顺序可能有多种，输出任意一解即可。

Example

Hint

样例一的解释已在题面中给出。