P5634 Digital Sorting [Enhanced Version]

**This problem is an enhanced version of [P5626](https://www.luogu.org/problem/P5626).** Xiao L has escaped from the virtual world!

While escaping, some digital beings also escaped. They are making a fuss and asking Xiao L to help sort them. The digital beings in the virtual world are invisible. Right now, Xiao L only knows selection sort, insertion sort, bubble sort, and merge sort. So Xiao L wants to ask: in the worst case, what is the minimum number of comparisons needed to make the sequence sorted? ------ [Template code for sorting](https://www.luogu.org/paste/fdtepscp)

The input has only one line: a positive integer $n$, the length of the sequence.

Output the minimum number of comparisons. Take the answer modulo $100000007$.

- **Sample $1$ explanation.** For a sequence of length $4$, merge sort splits it into $2$ groups, with $2$ elements in each group. The $2$ elements in each group are compared once. During merging, the worst-case number of comparisons is $3$, so the total is $3 + 1 + 1 = 5$. - **Constraints** For $10\%$ of the testdata, $n \leq 10^{18}$. For $20\%$ of the testdata, $n \leq 10^{100}$. For $50\%$ of the testdata, $n \leq 10^{1000}$. For $80\%$ of the testdata, $n \leq 10^{10000}$. For $100\%$ of the testdata, $n \leq 10^{100000}$. **Please pay attention to the time limit.** Translated by ChatGPT 5