P5634 数码排序【加强版】

**本题是[P5626](https://www.luogu.org/problem/P5626)的加强版** 小L从虚拟世界里出来啦！

逃出来的同时，也有一部分数码逃了出来，吵着闹着让小L帮他们排序。 虚拟世界的数码都是不可见的。 小L目前只会选择排序，插入排序，冒泡排序，归并排序。 所以小L想问他在最坏情况下最少需要几次比较，才能使序列有序。 ------ [排序的模板代码](https://www.luogu.org/paste/fdtepscp)

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

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

- **样例$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}$。 **请注意时限**