Description

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

Input Format

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

Output Format

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

4

5

5

8

Hint

• 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