Neko took final exam of C++ course. She remembered that she wrote down a piece of code as follow:
#include <iostream>
using namespace std;
void Swap(int * x, int * y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
int main(void) {
int n, l, r;
cin >> n >> l >> r;
int * a = new int(n);
for (int i=0;i<n;i++) a[i] = i;
Swap(a+l, a+r);
cout << a[0] << endl;
return 0;
} Since she just wrote it down unconsciously, she didn't remember the function of this code.
Now she is testing the code by inputting n, l, r.
n is a positive integer that she will choose in advance.
She will randomly choose an integer from 0 to n-1 (inclusive) as l.
She will randomly choose an integer from 0 to n-1 (inclusive) as r.
The probability of each number from 0 to n-1 be chosen is 1/n and the process of choosing l and r are independent.
Under such condition, can you calculate the expectation of output of the above program if n is provided?
An integer n (1<=n<=1000000).
Two integer p, q seperated by a single blank where p/q is the expectation of output and gcd(p,q)=1 (i.e., p and q are coprime).
If the answer is an integer p, output p, 1 seperated by a single blank (i.e., q = 1).