Algorithm Class - Algorithm Runtime 5

Time limit1sMemory limit512 MB

Summary

Given n, count how many times the innermost statement of a triple nested loop runs, and print the polynomial degree of that count.

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

Problem

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

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

The MenOfPassion algorithm is as follows.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            for k <- 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

On the first line, print the number of times code1 is executed.

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. However, if it cannot be expressed as a polynomial or the degree of the highest-order term is greater than 3, print 4.

Examples1

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