Problem Background

This problem is an enhanced version of P5626

Xiao L has come out from the virtual world!

Problem Description

While escaping, some digital entities also escaped and are clamoring for Xiao L to sort them.

The digital entities in the virtual world are invisible.

Xiao L currently knows only selection sort, insertion sort, bubble sort, and merge sort.

Therefore, Xiao L wants to know the minimum number of comparisons he needs in the worst case to make the sequence sorted.

Sorting template code

Input Format

The input consists of a single line, providing a positive integer $n$, representing the length of the sequence.

Output Format

Output the minimum number of comparisons, modulo $100000007$.

Sample Input and Output

Sample Input #1

4

Sample Output #1

5

Sample Input #2

5

Sample Output #2

8

Notes

• Sample 1 Explanation

For a sequence of length 4, using merge sort, divide into 2 groups, each with 2 elements. Each group compares once, and the worst-case comparison during merging is 3 times, so it is $3 + 1 + 1 = 5$.

• Data Range

For $10\%$ of the data, $n \leq 10^{18}$;

For $20\%$ of the data, $n \leq 10^{100}$;

For $50\%$ of the data, $n \leq 10^{1000}$;

For $80\%$ of the data, $n \leq 10^{10000}$;

For $100\%$ of the data, $n \leq 10^{100000}$.

Please note the time limit

见题面 Input 部分

见题面 Output 部分