题目背景

本题是P5626的加强版

小L从虚拟世界里出来啦！

题目描述

逃出来的同时，也有一部分数码逃了出来，吵着闹着让小L帮他们排序。

虚拟世界的数码都是不可见的。

小L目前只会选择排序，插入排序，冒泡排序，归并排序。

所以小L想问他在最坏情况下最少需要几次比较，才能使序列有序。

排序的模板代码

输入格式

输入仅有一行，给定一个正整数 $n$ ，表示序列的长度。

输出格式

输出最小的比较次数，答案对$100000007$取模。

4

5

5

8

提示

• 样例$1$解释

长度为$4$的序列归并调用，分成$2$组，一组$2$个元素。$2$个元素分别比较一次， 合并时最坏比较$3$次，所以是$3+1+1=5。$

• 数据范围

对于 $10\%$ 的数据，$n\leq10^{18}$；

对于 $20\%$ 的数据，$n\leq10^{100}$；

对于 $50\%$ 的数据，$n\leq10^{1000}$；

对于 $80\%$ 的数据，$n\leq10^{10000}$；

对于 $100\%$ 的数据，$n\leq10^{100000}$。

请注意时限