Algorithm Class - Algorithm Runtime 6

Time limit1sMemory limit512 MB

Summary

Count how many times the triple nested loop runs for a given n, then report the polynomial degree of that count.

Level: Easy2 of 10
Topics: Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

Seojun is once again a teaching assistant for the algorithm runtime class. Let us check through a problem whether the students understood what his father taught in class.

Given the input size n, print the runtime of the MenOfPassion algorithm in the same way as the sample output.

The MenOfPassion algorithm is as follows.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # code1
    return sum;
}

Input

The first line gives the input size n (1 ≤ n ≤ 500,000).

Output

Print the number of times code1 is executed on the first line.

On the second line, print the degree of the highest-order term when the number of times code1 is executed is expressed as a polynomial. If it cannot be expressed as a polynomial, or if the degree of the highest-order term is greater than 3, print 4.

Examples1

Example 1
Input
```
7
```
Expected output
```
35
3
```