For this Question: As always, Sid has come up with a new problem on Number Theory. Since it is too tricky to solve, can you help him. A bonus, you'll get a chapo for solving it right.
Given an integer n, let F(n) be the product of all positive integers i less or equal than n such that n and i are co-prime.
Now you're given an integer X, you need to find the sum of (F(i) modulo i) for all positive integers i less than or equal to X. If the answer is A, report the value of (A % 1000000007).The only line of input contains a single integer X.

Constraints
2 <= X <= 500000000Output a single integer, the required output for the problem.Sample Input
5

Sample Output
10

Sample Input
1000

Sample Output
128825, I have written this Solution Code: #include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define MOD 1000000007
#define INF 1000000000000000007LL

const int N = 100005;
 
 
#ifdef SWAPNIL07
#define trace(...) _f(#__VA_ARGS_, _VA_ARGS_)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif


const int M = 1000000;
int Lower[M+1], Higher[M+1];
char Used[M+1];
bool prime[100001];

void sieve(){
	memset(prime, true, sizeof(prime));
	for(int i=2; i<=100000; i++){
		if(!prime[i])
			continue;
		for(int j=i*i; j<=100000; j+=i)
			prime[j]=false;
	}
}

long long PrimePi(long long n)
{
    long long v = sqrt(n+1e-9), p, temp, q, j, end, i, d, t;
    for(int i=0;i<=M;i++)Used[i]=0;
    Higher[1] = n - 1;
    for(p = 2; p <= v; p++) {
        Lower[p] = p - 1;
        Higher[p] = (n/p) - 1;
    }
    for(p = 2; p <= v; p++) {
        if(Lower[p] == Lower[p-1])
            continue;
        temp = Lower[p-1];
        q = p * p;
        Higher[1] -= Higher[p] - temp;
        j = 1 + (p & 1);
        end = (v <= n/q) ? v : n/q;
        for(i = p + j; i <= 1 + end; i += j) {
            if(Used[i])
                continue;
            d = i * p;
            if(d <= v)
                Higher[i] -= Higher[d] - temp;
            else {
                t = n/d;
                Higher[i] -= Lower[t] - temp;
            }
        }
        if(q <= v)
            for(i = q; i <= end; i += p*j)
                Used[i] = 1;
        for(i = v; i >= q; i--) {
            t = i/p;
            Lower[i] -= Lower[t] - temp;
        }
    }
    return Higher[1];
}

int psum(int n){
  unordered_map<int, int> s;
  vector<int> v;
	int r = sqrt(n);
  for(int i=1; i<=r; i++){
  	int x = n/i;
  	v.pb(x);
  }
  int y = n/r;
  for(int i=y-1; i>0; i--){
  	v.pb(i);
  }
 	for(int i: v){
 		s[i] = (i*(i+1))/2 - 1;
 	}
 	for(int p=2; p<=r; p++){
 		if(s[p] > s[p-1]){
 			int sp = s[p-1];
 			int p2 = p*p;
 			for(int i: v){
 				if(i<p2)
 					break;
 				s[i] -= (p * (s[i/p] - sp));
 			}
 		}
 	}
 	return s[n];
}

signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int n; cin>>n;
   	int ans = psum(n)-2*PrimePi(n)+psum(n/2)*2-2*PrimePi(n/2)+n-1;
   	sieve();
   	for(int i=3; i<30000; i++){
   		if(!prime[i])
   			continue;
   		int x = i*i;
   		while(x <= n){
   			// trace(x);
   			ans += (x-2);
   			x *= i;
   		}
   		x = i*i*2;
   		while(x <= n){
   			// trace(x);
   			ans += (x-2);
   			x *= i;
   		}
   		ans %= MOD;
   	}
   	cout<<ans;
   	end_routine();
    return 0;
}, In this Programming Language: C++, Now tell me if this Code is compilable or not?