stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

int grt(int a,int b,int c)

{

    int p=__gcd(a,b);

    return __gcd(p,c);

}





int main()

{

    int p;

    cin>>p;

    long int sum=0;

    for(int i=1;i<=p;i++)

        for(int j=1;j<=p;j++)

            for(int k=1;k<=p;k++)

                sum+=grt(i,j,k);

    cout<<sum;



    return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define MAXN 100010

const long long M = 1000000007;

using namespace std;

long long dp[MAXN];

long long N, K;



int pot(long long a, long long b){

    long long ans = 1;

    while(b){

        if(b&1){

            ans = (ans * a) % M;

        }

        a = (a * a) % M;

        b >>= 1;

    }

    return ans;

}

int main(){

    ios::sync_with_stdio(0);

    cin.tie(0);

    N = 3;

    cin >> K;

    long long ans = 0;

    for(int i = K; i > 0; i--){

        dp[i] = pot(K / i, N);

        for(int j = i+i; j <= K; j += i){

            dp[i] -= dp[j];

        }

        dp[i] = ((dp[i] % M) + M) % M;

        ans += i * dp[i];

        ans %= M;

    }

    

    ans = ((ans % M) + M) % M;

    cout << ans << "\n";

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<stdio.h>

#include<math.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<vector>

#include<string>

#define gc getchar()

using namespace std;

#define kk putchar(32)

#define fup(i,a,b) for(int i=a,i##e=b;i<=i##e;++i)

#define fdn(i,a,b) for(int i=a,i##e=b;i>=i##e;--i)

#define hh putchar(10)

#define ll long long

struct zio {

	template<class T>inline zio & operator >>(T &x) {

		T f(1); char a;

		while((a=getchar())<48)if(a==45)f=-1;

		for(x=a^48;(a=getchar())>47;x=(x<<3)+(x<<1)+(a^48));

		x*=f; return *this;

	}

	template<class T>inline zio & operator <<(T x) {

		if(sizeof(x)==sizeof(char))putchar(x);

		else {

			if(x<0) x=-x,putchar(45);

			if(x>99) {

				static char za[20]; int i=0;

				while(x) za[i++]=x%10,x/=10;

				while(i--) putchar(za[i]+48);

			} else if (x>9) putchar(x/10+48),putchar(x%10+48);

			else putchar(x+48);

		}

	}

} io;



int gcd(int a,int b){

	return b?gcd(b,a%b):a;

}

void Main()

{

	int k;

	cin>>k;

	ll ans=0;

	fup(i,1,k)fup(j,1,k)fup(x,1,k)

		ans+=gcd(gcd(i,j),x);

	cout<<ans;

}











int main()

{

	Main();

	return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define MAXN 100010

const long long M = 1000000007;

using namespace std;

long long dp[MAXN];

long long N, K;



int pot(long long a, long long b){

    long long ans = 1;

    while(b){

        if(b&1){

            ans = (ans * a) % M;

        }

        a = (a * a) % M;

        b >>= 1;

    }

    return ans;

}

int main(){

    ios::sync_with_stdio(0);

    cin.tie(0);

    N = 3;

    cin >> K;

    long long ans = 0;

    for(int i = K; i > 0; i--){

        dp[i] = pot(K / i, N);

        for(int j = i+i; j <= K; j += i){

            dp[i] -= dp[j];

        }

        dp[i] = ((dp[i] % M) + M) % M;

        ans += i * dp[i];

        ans %= M;

    }

    

    ans = ((ans % M) + M) % M;

    cout << ans << "\n";

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<stdio.h>

#include<algorithm>

#include<bits/stdc++.h>

using namespace std;

int gcd(int x, int y)

{

    if(y==0)

        return x;

    return gcd(y, x%y);

}

int main()

{

    int a,b,c=0,i,j,k,n;

    cin>>n;

    for(i=1;i<=n;i++){

        for(j=1;j<=n;j++){

            for(k=1;k<=n;k++){

                c=c+gcd(gcd(i,j),k);

            }

        }

    }

    cout<<c<<endl;



}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define MAXN 100010

const long long M = 1000000007;

using namespace std;

long long dp[MAXN];

long long N, K;



int pot(long long a, long long b){

    long long ans = 1;

    while(b){

        if(b&1){

            ans = (ans * a) % M;

        }

        a = (a * a) % M;

        b >>= 1;

    }

    return ans;

}

int main(){

    ios::sync_with_stdio(0);

    cin.tie(0);

    N = 3;

    cin >> K;

    long long ans = 0;

    for(int i = K; i > 0; i--){

        dp[i] = pot(K / i, N);

        for(int j = i+i; j <= K; j += i){

            dp[i] -= dp[j];

        }

        dp[i] = ((dp[i] % M) + M) % M;

        ans += i * dp[i];

        ans %= M;

    }

    

    ans = ((ans % M) + M) % M;

    cout << ans << "\n";

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define be(v) (v).begin(),(v).end()

#define pb(q) push_back(q)

typedef long long ll;

using namespace std;

const ll mod=1000000007;

#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;



int main() {

    cin.tie(0);

    cout.tie(0);

    ios::sync_with_stdio(false);

    int k;

    cin>>k;

    ll sum=0;

    for(int i=1;i<=k;i++){

    	for(int j=1;j<=k;j++){

    		for(int x=1;x<=k;x++){

    			sum+=__gcd(i,__gcd(j,x));

    		}

    	}

    }

    cout << sum <<endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define be(v) (v).begin(),(v).end()

#define pb(q) push_back(q)

typedef long long ll;

using namespace std;

const ll mod=1000000007;

#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;



long long modpow(long long a, long long n) {

    long long res = 1;

    while (n > 0) {

        if (n & 1) res = res * a % mod;

        a = a * a % mod;

        n >>= 1;

    }

    return res;

}



int main() {

    cin.tie(0);

    cout.tie(0);

    ios::sync_with_stdio(false);

    ll n,k;

    cin>>k;n=3;

    ll a[k+1];

    for(int i=1;i<=k;i++){

    	ll num=k/i;

    	a[i]=modpow(num,n);

    }

    for(int i=k;i>=1;i--){

    	for(int j=i*2;j<=k;j+=i){

    		(a[i]-=a[j])%=mod;

    	}

    }

    ll ans=0;

    for(int i=1;i<=k;i++){

    	(ans+=(a[i]*i)%mod)%=mod;

    }

    ans+=mod;

    ans%=mod;

    cout << ans <<endl;

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



inline long gcc(int a, int b, int c)

{

	int n = 2;

	int v = 1;

	while(n <= a && n <= b && n <= c){

		if(a % n == 0 && b % n == 0 && c % n == 0){

			a /= n;

			b /= n;

			c /= n;

			v *= n;

		}else{

			n++;

		}

	}

	

	return v;

}



int main() 

{

	int K;

	cin >> K;

	

	long sum = 0;

	

	for(int a = 1; a <= K; a++){

      for(int b = 1; b <= K; b++){

        for(int c = 1; c <= K; c++){

            sum += gcc(a, b, c);

        }

      }

	}



	cout << sum << endl;

	

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

 

inline long gcc(int a, int b, int c)

{

	int n = 2;

	int v = 1;

	while(n <= a && n <= b && n <= c){

		if(a % n == 0 && b % n == 0 && c % n == 0){

			a /= n;

			b /= n;

			c /= n;

			v *= n;

		}else{

			n++;

		}

	}

	

	return v;

}

 

int main() 

{

	int K;

	cin >> K;

	

	long sum = 0;

	

	for(int a = 1; a <= K; a++){

      for(int b = 1; b < a; b++){

        for(int c = 1; c < b; c++){

            sum += 6 * gcc(a, b, c);

        }

      }

	}

 

	for(int a = 1; a <= K; a++){

      for(int b = 1; b <= K; b++){

        	if(a==b) continue;

            int c = b;

            sum += 3 * gcc(a, b, c);

      }

	}

 

	for(int a = 1; a <= K; a++){

	  int b = a;

	  int c = b;

      sum += gcc(a, b, c);

	}

 

	cout << sum << endl;

	

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <sstream>

#include <queue>

#include <deque>

#include <bitset>

#include <iterator>

#include <list>

#include <stack>

#include <map>

#include <unordered_map>

#include <set>

#include <unordered_set>

#include <functional>

#include <numeric>

#include <utility>

#include <limits>

#include <time.h>

#include <math.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <assert.h>



using namespace std;



#define FOR(i,n) for(int i = 0; i < n; i++)

#define FORa(i,a,b) for(int i = a; i < b; i++)

#define pb(x) push_back(x)

#define mp(a, b) make_pair(a, b)

#define F first

#define S second

#define SORT(a,n) sort(begin(a), begin(a) + n)

#define VSORT(v) sort(v.begin(), v.end())

#define MAX 1000000

#define ll long long

#define LOW(s) transform(s.begin(),s.end(),s.begin(),::tolower)

#define UP(s) transform(s.begin(),s.end(),s.begin(),::toupper)



//-------------------------------------------------------//



int gcd(int a, int b) {

		if(a == 0) return b;

		return gcd(b%a, a);

}



int main() {

	ll k, sum = 0;

	cin >> k;

	

	for(int a = 1; a <= k; a++) {

		for(int b = 1; b <= k; b++) {

			for(int c = 1; c <= k; c++) sum += gcd(gcd(a,b),gcd(b,c));

		}

	}

	

	cout << sum << endl;

  

	return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <sstream>

#include <queue>

#include <deque>

#include <bitset>

#include <iterator>

#include <list>

#include <stack>

#include <map>

#include <unordered_map>

#include <set>

#include <unordered_set>

#include <functional>

#include <numeric>

#include <utility>

#include <limits>

#include <time.h>

#include <math.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <assert.h>



using namespace std;



#define FOR(i,n) for(int i = 0; i < n; i++)

#define FORa(i,a,b) for(int i = a; i < b; i++)

#define pb(x) push_back(x)

#define mp(a, b) make_pair(a, b)

#define F first

#define S second

#define SORT(a,n) sort(begin(a), begin(a) + n)

#define VSORT(v) sort(v.begin(), v.end())

#define MAX 1000000

#define ll long long

#define LOW(s) transform(s.begin(),s.end(),s.begin(),::tolower)

#define UP(s) transform(s.begin(),s.end(),s.begin(),::toupper)



//-------------------------------------------------------//



int gcd(int a, int b) {

		if(a == 0) return b;

		return gcd(b%a, a);

}



int main() {

	ll k, sum = 0;

	cin >> k;

	

	for(int a = 1; a <= k; a++) {

		for(int b = 1; b <= k; b++) {

			int temp = gcd(a,b);

			for(int c = 1; c <= k; c++) sum += gcd(temp,c);

		}

	}

	

	cout << sum << endl;

  

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>



#define ll long long

#define fornum(A,B,C) for(A=B;A<C;++A)

#define pii pair<int,int>

#define pll pair<ll,ll>



using namespace std;



/////////////////////////////////////////////////////

ll K;

ll i, j, k,ans;

ll gcd(ll a,ll b){

    if(b==0)

        return a;

    return gcd(b, a % b);

}

int main(){

    scanf("%lld", &K);

    fornum(i,0,K){

        fornum(j,0,K){

            fornum(k,0,K){

                ans += gcd(gcd(i + 1, j + 1), k + 1);

            }

        }

    }

    printf("%lld\n", ans);

    return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>



#define ll long long

#define fornum(A,B,C) for(A=B;A<C;++A)

#define pii pair<int,int>

#define pll pair<ll,ll>



using namespace std;



/////////////////////////////////////////////////////

ll K;

ll mk[222];

ll i, j, k,ans;

ll gcd(ll a,ll b){

    if(b==0)

        return a;

    return gcd(b, a % b);

}

int main(){

    scanf("%lld", &K);

    fornum(i,1,K+1){

        fornum(j,1,K+1){

            ++mk[gcd(i, j)];

        }

    }

    fornum(i,1,K+1){

        fornum(j,1,K+1){

            ans += mk[j] * gcd(i, j);

        }

    }

    printf("%lld\n", ans);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//#include <bits/stdc++.h>

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

#include <cmath>

#include <algorithm>

#include <map>

#include <iomanip>

#include <stdlib.h>

#include <stdio.h>

#include <queue>

#include <deque>

#include <set>

#include <stack>

#include <time.h>

 

using namespace std;

 

typedef long long ll;

typedef long double ld;

typedef pair<int, int> Pii;

typedef pair<int, ll> Pil;

typedef pair<ll, ll> Pll;

typedef pair<ll, int> Pli;

 

const ll inf = 1e9 + 7;

const ll Mod = 998244353;

const ll INF = 1ll << 62;

const double PI = 2 * asin(1);



int GCD(int A, int B){

  if (A < B) swap(A, B);

  while (A % B != 0){

    A = A % B;

    swap(A, B);

  }

  return B;

}



int main(){

  int K; cin >> K;



  int ans = 0;

  for (int i = 1; i <= K; i++){

    for (int j = 1; j <= K; j++){

      for (int k = 1; k <= K; k++){

        ans += GCD(i, GCD(j, k));

      }

    }

  }

  cout << ans << endl;





  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;

 

typedef long long ll;

typedef long double ld;

typedef pair<int, int> Pii;

typedef pair<int, ll> Pil;

typedef pair<ll, ll> Pll;

typedef pair<ll, int> Pli;



#define fi first

#define se second



const ll MOD = 1e9 + 7;

const ll MOD2 = 998244353;

const ll MOD3 = 1812447359;

const ll INF = 1ll << 62;

const double PI = 2 * asin(1);



void yes() {printf("yes\n");}

void no() {printf("no\n");}

void Yes() {printf("Yes\n");}

void No() {printf("No\n");}

void YES() {printf("YES\n");}

void NO() {printf("NO\n");}



ll Pow(ll A, ll N){

  if (N == 0) return 1;

  if (N % 2 == 0) return Pow(A * A % MOD, N / 2);

  else return Pow(A * A % MOD, N / 2) * A % MOD;

}



ll N, K;

ll DP[int(1e5+5)];



int main(){

  N = 3;

  cin >> K;

  for (ll i = K; i >= 1; i--){

    DP[i] = Pow(K / i, N);



    ll sum = 0;

    for (ll j = 2 * i; j <= K; j += i){

      sum += DP[j]; sum %= MOD;

    }

    DP[i] -= sum; DP[i] %= MOD;

    if (DP[i] < 0) DP[i] += MOD;

  }



  ll ans = 0;

  for (ll i = 1; i <= K; i++){

    ans += i * DP[i]; ans %= MOD; 

  }

  cout << ans << endl;



  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

 

typedef long long ll;

typedef long double ld;

typedef pair<int, int> Pii;

typedef pair<int, ll> Pil;

typedef pair<ll, ll> Pll;

typedef pair<ll, int> Pli;



#define fi first

#define se second



const ll MOD = 1e9 + 7;

const ll MOD2 = 998244353;

const ll MOD3 = 1812447359;

const ll INF = 1ll << 62;

const double PI = 2 * asin(1);



void yes() {printf("yes\n");}

void no() {printf("no\n");}

void Yes() {printf("Yes\n");}

void No() {printf("No\n");}

void YES() {printf("YES\n");}

void NO() {printf("NO\n");}



ll GCD(int A, int B){

  if (A < B) swap(A, B);

  while (A % B != 0){

    A %= B;

    swap(A, B);

  }

  return B;

}



int main(){

  int K; cin >> K;

  ll ans = 0;

  for (int i = 1; i <= K; i++){

    for (int j = 1; j <= K; j++){

      for (int k = 1; k <= K; k++){

        ans += GCD(i, GCD(j, k));

      }

    }

  }

  cout << ans << endl;



  return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;

 

typedef long long ll;

typedef long double ld;

typedef pair<int, int> Pii;

typedef pair<int, ll> Pil;

typedef pair<ll, ll> Pll;

typedef pair<ll, int> Pli;



#define fi first

#define se second



const ll MOD = 1e9 + 7;

const ll MOD2 = 998244353;

const ll MOD3 = 1812447359;

const ll INF = 1ll << 62;

const double PI = 2 * asin(1);



void yes() {printf("yes\n");}

void no() {printf("no\n");}

void Yes() {printf("Yes\n");}

void No() {printf("No\n");}

void YES() {printf("YES\n");}

void NO() {printf("NO\n");}



ll Pow(ll A, ll N){

  if (N == 0) return 1;

  if (N % 2 == 0) return Pow(A * A % MOD, N / 2);

  else return Pow(A * A % MOD, N / 2) * A % MOD;

}



ll N, K;

ll DP[int(1e5+5)];



int main(){

  N = 3;

  cin >> K;

  for (ll i = K; i >= 1; i--){

    DP[i] = Pow(K / i, N);



    ll sum = 0;

    for (ll j = 2 * i; j <= K; j += i){

      sum += DP[j]; sum %= MOD;

    }

    DP[i] -= sum; DP[i] %= MOD;

    if (DP[i] < 0) DP[i] += MOD;

  }



  ll ans = 0;

  for (ll i = 1; i <= K; i++){

    ans += i * DP[i]; ans %= MOD; 

  }

  cout << ans << endl;



  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#include<algorithm>

using namespace std;

int main(){

  int K;

  cin >> K;

  int sum = 0;

  for (int i = 1; i <= K; i++){

    for (int j = 1; j <= K;j++){

      for (int l = 1; l <= K;l++){

        vector<int> data(3);

        data.at(0) = i;

        data.at(1) = j;

        data.at(2) = l;

        sort(data.begin(), data.end());

        int a = __gcd(data[2], data[1]);

        sum += __gcd(data[0], a);

        //cout << __gcd(data[0], a) << endl;

      }

    }

  }

  cout << sum << endl;

}

// Optimized solution to the same problem (faster):


#include<bits/stdc++.h>

using namespace std;

int main(){

  int res=0;

  int K;cin>>K;

  for(int i=1;i<=K;i++){

    for(int j=1;j<=K;j++){

      for(int l=1;l<=K;l++){

        int tmp=__gcd(i,j);

        res+=__gcd(tmp,l);

      }

    }

  }

  cout<<res<<endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#define il inline

#define re register

#define fo(i,j,k) for(register int i=j;i<=k;i++)

#define do(i,j,k) for(register int i=j;i>=k;i--) 

#define inf 0x7fffffff

typedef long long ll;

using namespace std;

il ll read()

{

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}

	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return f*x;	

}

int n; 

ll sum;

int gcd(int a,int b)

{

	if(b==0) return a;

	return gcd(b,a%b);

}

int main()

{

	cin>>n;

	fo(i,1,n)

	{

		fo(j,1,n)

		{

			fo(k,1,n)

			{

				sum+=gcd(i,gcd(j,k));

			} 

		}

	}

	cout<<sum;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#define il inline

#define re register

#define fo(i,j,k) for(register int i=j;i<=k;i++)

#define do(i,j,k) for(register int i=j;i>=k;i--) 

#define inf 0x7fffffff

typedef long long ll;

using namespace std;

il ll read()

{

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}

	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return f*x;	

}

/*int h[200010],v[200010],dis[200010];

struct edge

{

	int v,w,next;

}e[200010*2];

il void add(int u,int v,int w)

{

	e[++cnt].v=v;

	e[cnt].w=w;

	e[cnt].next=h[u];

	h[u]=cnt;

}*/

ll n,k,ans;

ll dp[100010];

const ll mod=1e9+7;

ll cal(ll a,ll b)

{

    ll ret=1;

    while(b)

    {

        if(b&1) ret=(ret*a)%mod;

        a=(a*a)%mod;

        b>>=1LL;

    }

    return ret;

}

int main()

{

	//easy

    n=3,k=read();

    for(re ll i=k;i>=1;i--)

    {

        ll num=k/i;

        dp[i]=cal(num,n);

        for(ll j=2*i;j<=k;j+=i)

        {

            dp[i]=(dp[i]-dp[j]+mod)%mod;

        }

        ans=(ans+dp[i]*i)%mod;

    }

    printf("%lld\n",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#define il inline

#define re register

#define fo(i,j,k) for(register int i=j;i<=k;i++)

#define do(i,j,k) for(register int i=j;i>=k;i--) 

#define inf 0x7fffffff

typedef long long ll;

using namespace std;

il ll read()

{

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}

	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return f*x;	

}

int n; 

ll sum;

int gcd(int a,int b)

{

	if(b==0) return a;

	return gcd(b,a%b);

}

int main()

{

	cin>>n;

	fo(i,1,n)

	{

		fo(j,1,n)

		{

			fo(k,1,n)

			{

				sum+=gcd(i,gcd(j,k));

			} 

		}

	}

	cout<<sum;

	return 0;

}


// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#define il inline

#define re register

#define fo(i,j,k) for(register int i=j;i<=k;i++)

#define do(i,j,k) for(register int i=j;i>=k;i--) 

#define inf 0x7fffffff

typedef long long ll;

using namespace std;

il ll read()

{

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}

	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return f*x;	

}

/*int h[200010],v[200010],dis[200010];

struct edge

{

	int v,w,next;

}e[200010*2];

il void add(int u,int v,int w)

{

	e[++cnt].v=v;

	e[cnt].w=w;

	e[cnt].next=h[u];

	h[u]=cnt;

}*/

ll n,k,ans;

ll dp[100010];

const ll mod=1e9+7;

ll cal(ll a,ll b)

{

    ll ret=1;

    while(b)

    {

        if(b&1) ret=(ret*a)%mod;

        a=(a*a)%mod;

        b>>=1LL;

    }

    return ret;

}

int main()

{

	//easy

    n=3,k=read();

    for(re ll i=k;i>=1;i--)

    {

        ll num=k/i;

        dp[i]=cal(num,n);

        for(ll j=2*i;j<=k;j+=i)

        {

            dp[i]=(dp[i]-dp[j]+mod)%mod;

        }

        ans=(ans+dp[i]*i)%mod;

    }

    printf("%lld\n",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;



int gcd (int a,int b,int c);

int main(){

    ll ans = 0;

    int n;

    cin >> n;



    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= n; j++){

            for(int k = 1; k <= n; k++ ){

                ans +=gcd(k,j,i);

            }

        }

    }



    cout << ans << endl;

    

}



int gcd(int a,int b,int c){

    int minn = min({a,b,c});

    int ans = 0;

    for(int i = 1; i <= minn; i++){

        if(a % i == 0 && b % i == 0 && c % i == 0){

            ans = i;

        }

    }



    return ans;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){

    ll ans = 0;

    int n;

    cin >> n;



    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= n; j++){

            for(int k = 1; k <= n; k++ ){

                ans +=__gcd(k,__gcd(j,i));

            }

        }

    }



    cout << ans << endl;

    

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <iomanip>

#include <algorithm>

#include <vector>

#include <set>

#include <cmath>

#define rep(i,n) for (int i = 0; i < n; ++i)

using namespace std;

using ll = long long;

using P = pair<int,int>;





int gcd(int a, int b, int c) {

  int ans = 1;

  for (int i = 1; i <= min(min(a,b), c); ++i) {

    if (a % i == 0) {

      if (b % i == 0) {

        if (c % i == 0){

          ans = i;

        }

      }

    }

  }

  return ans;

}



int main() {

  int K;

  cin >> K;

  int ans = 0;

  for (int a = 1; a <= K; a++) {

    for (int b = 1; b <= K; b++) {

      for (int c = 1; c <= K; c++) {

        ans += gcd(a, b, c);

      }

    }

  }

  cout << ans << endl;

  return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <iomanip>

#include <algorithm>

#include <vector>

#include <set>

#include <cmath>

#define rep(i,n) for (int i = 0; i < n; ++i)

using namespace std;

using ll = long long;

using P = pair<int,int>;



int gcd(int a, int b) {

  if (a % b == 0) return b;

  return gcd(b, a % b);

}



int gcd(int a, int b, int c) {

  int ans = 1;

  for (int i = 1; i <= min(min(a,b), c); ++i) {

    if (a % i == 0) {

      if (b % i == 0) {

        if (c % i == 0){

          ans = i;

        }

      }

    }

  }

  return ans;

}



int main() {

  int K;

  cin >> K;

  int ans = 0;

  for (int a = 1; a <= K; a++) {

    for (int b = 1; b <= K; b++) {

      for (int c = 1; c <= K; c++) {

        ans += gcd(gcd(a, b), c);

      }

    }

  }

  cout << ans << endl;

  return 0;

}

// Fastest known solution for this problem: