Algorithm Class - Algorithm Runtime 3

Time limit1sMemory limit512 MB

Summary

Given n, count how many times the innermost statement of a double loop runs and report the degree of that count as a polynomial.

Level: Easy1 of 10
Topics: Math, Implementation, Simulation
Solved: No attempts yet

Problem

Seojun is once again the 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 format 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
            sum <- sum + A[i] × A[j]; # 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 leading term when the number of executions of code1 is expressed as a polynomial. If it cannot be expressed as a polynomial, or if the degree of the leading term is greater than 3, print 4.

Examples1

Example 1
Input
```
7
```
Expected output
```
49
2
```