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).