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



using namespace std;

typedef long long ll;



const ll MOD = 1e9 + 7;



int cnt[65][2];



int main(){

	memset(cnt,0,sizeof cnt);

	int n; cin >> n;

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

		ll x; cin >> x;

		for(int j=0; j<60; j++){

			if(x & ((ll)1 << j)) cnt[j][1]++;

			else cnt[j][0]++;

		}

	}

	ll ans = 0, pw = 1;

	for(int i=0; i<60; i++){

		pw %= MOD;

		ans += pw * (((ll)cnt[i][0] * cnt[i][1]) % MOD);

		ans %= MOD;

		pw *= (ll)2;

	}

	cout << ans << endl;

	return 0;

}

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

long long int a[600000]={0};

#define mod 1000000007

int main()

{

	long long int n,i,j,s,ans,d;

	scanf("%lld",&n);

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

		scanf("%lld",&a[i]);

		

	} 

	d=1;ans=0;

	for(i=0;i<60;i++)

	{

		s=0;

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

		{



			if(a[j]&1)

			s++;

			a[j]>>=1;

		}



		ans+=((s*(n-s)%mod)*d)%mod;

		d*=2;

		d%=mod;

	}

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

 } 

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

#include<string>

#include<sstream>

#include<algorithm>

#include<vector>

#include<iomanip>

#include<cmath>

#include<complex>

#include<queue>

#include<deque>

#include<stack>

#include<map>

#include<set>

#include<bitset>

#include<functional>

#include<numeric>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;

#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )

#define rep(i,n) REP(i,0,n)

using ll = long long;

const int inf=1e9+7;

const ll longinf=1LL<<60 ;

const ll mod=1e9+7 ;

int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};





const int MAX = 510000;



// 二項係数計算

long long com(ll n){

    ll k = 2;

    if (n < k) return 0;

    if (n < 0 || k < 0) return 0;

    return n*(n-1)/2;

}



int main()

{



    ll N;

    cin >> N;

    vector<ll> A;

    ll same[200005] = {};

    ll done[200005] = {};



    for(ll i=0; i<N; ++i)

    {

        ll tmp;

        cin >> tmp;

        A.push_back(tmp);

        ++same[tmp];

    }



    ll all = 0;

    for(ll i=0; i<N; ++i)

    {

        if(done[A[i]]==1) continue;

        else

        {

            done[A[i]] = 1;

            all += com(same[A[i]]);

        }

    }



    for(ll i=0; i<N; ++i)

    {

        cout << all - com(same[A[i]]) + com(same[A[i]]-1) << endl;

    }



    return 0;

}


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

#include<string>

#include<sstream>

#include<algorithm>

#include<vector>

#include<iomanip>

#include<cmath>

#include<complex>

#include<queue>

#include<deque>

#include<stack>

#include<map>

#include<set>

#include<bitset>

#include<functional>

#include<numeric>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;

#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )

#define rep(i,n) REP(i,0,n)

using ll = long long;

const int inf=1e9+7;

const ll longinf=1LL<<60 ;

const ll mod=1e9+7 ;

int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};



// 二項係数計算

long long com(ll n){

    ll k = 2;

    if (n < k) return 0;

    if (n < 0 || k < 0) return 0;

    return n*(n-1)/2;

}



int main()

{



    ll N;

    cin >> N;

    vector<ll> A;

    int same[200005] = {};

    int done[200005] = {};



    for(ll i=0; i<N; ++i)

    {

        ll tmp;

        cin >> tmp;

        A.push_back(tmp);

        ++same[tmp];

    }



    ll all = 0;

    for(ll i=0; i<N; ++i)

    {

        if(done[A[i]]==1) continue;

        else

        {

            done[A[i]] = 1;

            all += com(same[A[i]]);

        }

    }



    for(ll i=0; i<N; ++i)

    {

        cout << all - com(same[A[i]]) + com(same[A[i]]-1) << endl;

    }



    return 0;

}


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

#include<string>

#include<sstream>

#include<algorithm>

#include<vector>

#include<iomanip>

#include<cmath>

#include<complex>

#include<queue>

#include<deque>

#include<stack>

#include<map>

#include<set>

#include<bitset>

#include<functional>

#include<numeric>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;

#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )

#define rep(i,n) REP(i,0,n)

using ll = long long;

const int inf=1e9+7;

const ll longinf=1LL<<60 ;

const ll mod=1e9+7 ;

int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};



// 二項係数計算

long long com(ll n){

    ll k = 2;

    if (n < k) return 0;

    if (n < 0 || k < 0) return 0;

    return n*(n-1)/2;

}



int main()

{



    ll N;

    cin >> N;

    vector<ll> A;

    ll same[200005] = {};

    int done[200005] = {};



    for(ll i=0; i<N; ++i)

    {

        ll tmp;

        cin >> tmp;

        A.push_back(tmp);

        ++same[tmp];

    }



    ll all = 0;

    for(ll i=0; i<N; ++i)

    {

        if(done[A[i]]==1) continue;

        else

        {

            done[A[i]] = 1;

            all += com(same[A[i]]);

        }

    }



    for(ll i=0; i<N; ++i)

    {

        cout << all - com(same[A[i]]) + com(same[A[i]]-1) << endl;

    }



    return 0;

}


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

#include<string>

#include<sstream>

#include<algorithm>

#include<vector>

#include<iomanip>

#include<cmath>

#include<complex>

#include<queue>

#include<deque>

#include<stack>

#include<map>

#include<set>

#include<bitset>

#include<functional>

#include<numeric>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;

#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )

#define rep(i,n) REP(i,0,n)

using ll = long long;

const int inf=1e9+7;

const ll longinf=1LL<<60 ;

const ll mod=1e9+7 ;

int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};



// 二項係数計算

long long com(ll n){

    ll k = 2;

    if (n < k) return 0;

    if (n < 0 || k < 0) return 0;

    return n*(n-1)/2;

}



int main()

{



    ll N;

    cin >> N;

    vector<ll> A;

    int same[200005] = {};

    int done[200005] = {};



    for(ll i=0; i<N; ++i)

    {

        ll tmp;

        cin >> tmp;

        A.push_back(tmp);

        ++same[tmp];

    }



    ll all = 0;

    for(ll i=0; i<N; ++i)

    {

        if(done[A[i]]==1) continue;

        else

        {

            done[A[i]] = 1;

            all += com(same[A[i]]);

        }

    }



    for(ll i=0; i<N; ++i)

    {

        cout << all - com(same[A[i]]) + com(same[A[i]]-1) << endl;

    }



    return 0;

}


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

#include <iostream>

using namespace std;

long long Cou[202000];

long long Num[202000];

long long Cal[202000];

long long book[202000];

void cal() {

    Cal[1] = 0;

    Cal[2] = 1;

    for (long long i = 3; i <= 202000; i++) {

        Cal[i] = Cal[i - 1] + i - 1;

    }

    return;

}

int main() {

    long long N;

    cal();

    while (cin >> N) {

        memset(Cou, 0, sizeof(Cou));

        memset(book, 0, sizeof(book));

        for (long long i = 1; i <= N; i++) {

            cin >> Num[i];

            Cou[Num[i]]++;

        }

        long long tempAns = 0;

        for (long long i = 1; i <= N; i++) {

            if (book[Num[i]] == 0) {

                tempAns += Cal[Cou[Num[i]]];

                book[Num[i]]++;

            }

        }

        // cout << "#" << tempAns << endl;

        for (long long i = 1; i <= N; i++) {

            cout << tempAns - Cal[Cou[Num[i]]] + Cal[Cou[Num[i]] - 1] << endl;

        }

    }

    return 0;

}

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

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=200000+50;

int n;

int a[maxn];

int f[maxn];

int vis[maxn];

int tot;

int main()

{

    scanf("%d",&n);

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

    {

        scanf("%d",&a[i]);

        if(vis[a[i]]) f[vis[a[i]]]++;

        else

        {

            vis[a[i]]=++tot;

            f[vis[a[i]]]++;

        }    

    }   

    long long ans=0;

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

    {

        long long b=f[i];

        ans+=b*(b-1);

    }



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

    {

        long long b=f[vis[a[i]]];

        cout<<ans/2-b+1<<'\n';

    }

    return 0;



}

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

#include<iostream>

#include<stdio.h>

typedef long long ll;

using namespace std;



const ll mod = 998244353;

const ll inv2 = (mod + 1) >> 1;

ll poww(ll a, ll b){

	ll res = 1;

	while (b){

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

		a = a*a%mod;

		b >>= 1;

	}

	return res;

}



int n, s;

int a[3005];

ll c[3005];

int main(){

	cin >> n >> s;

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

		cin >> a[i];

		c[i] = 0;

	}

	c[0] = poww(2, n);

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

		for (int j = 3000 - a[i]; j >= 0; j--){

			c[j + a[i]] = (c[j + a[i]] + c[j]*inv2) % mod;

		}

		continue;

	}

	cout << c[s] << endl;

	return 0;

}

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

using namespace std;

typedef long long ll;

const int MAXN = 3e3 + 5;

const int INF = 0x7f7f7f7f;

const ll p = 998244353;

#define DEBUG(x) cout << x << '\n'



int n, s, t, f[MAXN];

ll f_pow(ll a, ll b){

    ll res = 1;

    for(; b; b >>= 1, a = a * a % p)

        if(b & 1) res = res * a % p;

    return res;

}

int main(){

#ifdef Irene

    freopen("in.txt", "r", stdin);

#endif // Irene

    ios::sync_with_stdio(false);



    cin >> n >> s;

    f[0] = f_pow(2, n);

    ll inv2 = f_pow(2, p - 2);

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

        cin >> t;

        for(int j = s - t; j >= 0; j--)

            f[j+t] = (f[j+t] + f[j] * inv2) % p;

    }

    cout << f[s];

}


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

#define watch(x) cout << (#x) << " is " << (x) << endl

const int mod = 998244353;



using namespace std;



int s, n;



void knapsackSubset()		//coeff x^s du polynome Pi(2+x^ai)

{	

	scanf("%d%d", &n, &s);

	int x;

	vector<long long> coeff(3000, 0);

	cin >> x;

	coeff[0] = 2, coeff[x] = 1;

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

	{

		scanf("%d", &x);

		vector<long long>oldCo = coeff; //ancient coordonnes, (ne pas oublier qu'on mulitplie par 2, on doit se rappeler des ancierts coo, quitte a diviser par 2 aussi)

		for (int j = 0; j <= s; j++)

		{

			coeff[j] = (2*coeff[j])%mod;

			if (j >= x)

				coeff[j] += oldCo[j-x];

			coeff[j] %= mod;

		}

	} 

	cout << coeff[s] << endl;	

}



int main()

{

	#ifdef ME

		freopen("input.txt", "r", stdin);

		freopen("output.txt", "w", stdout);

	#endif



	knapsackSubset();

	return 0;

}






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

#define watch(x) cout << (#x) << " is " << (x) << endl

const int mod = 998244353;



using namespace std;



int s, n;



void knapsackSubset()		//coeff x^s du polynome Pi(2+x^ai)

{	

	scanf("%d%d", &n, &s);

	int x;

	vector<long long> coeff(s+1, 0);

	cin >> x;

	coeff[0] = 2;

	if (x <= s)

	 coeff[x] = 1;

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

	{

		scanf("%d", &x);

		vector<long long>oldCo = coeff; //ancient coordonnes, (ne pas oublier qu'on mulitplie par 2, on doit se rappeler des ancierts coo, quitte a diviser par 2 aussi)

		for (int j = 0; j <= s; j++)

		{

			coeff[j] = (2*coeff[j])%mod;

			if (j >= x)

				coeff[j] += oldCo[j-x];

			coeff[j] %= mod;

		}

	} 

	cout << coeff[s] << endl;	

}



int main()

{

	#ifdef ME

		freopen("input.txt", "r", stdin);

		freopen("output.txt", "w", stdout);

	#endif



	knapsackSubset();

	return 0;

}






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

using namespace std;



int64_t MOD = 998244353;



int64_t N_MAX = 3010;



int64_t dp[3010][3010];



//modの割り算

// a/bをa*modint(b,MOD) %MODに変換

long long modinv(long long a, long long m) {

  long long b = m, u = 1, v = 0;

  while (b) {

    long long t = a / b;

    a -= t * b; swap(a, b);

    u -= t * v; swap(u, v);

  }

  u %= m;

  if (u < 0) u += m;

  return u;

}



//繰り返し二乗法

int64_t powmod(int64_t x, int64_t n) { 

  int64_t ans = 1;

  while (n > 0) {

    if ((n & 1) == 1) {

      ans = ans * x;

      ans %= MOD;

    }

    x = x * x;//一周する度にx, x^2, x^4, x^8となる

    x %= MOD;

    n >>= 1; //桁をずらす n = n >> 1

  }

  return ans;

}



int main(){

  int64_t N, S;

  cin >> N >> S;

  vector<int64_t> vec(N);

  for(int i=0; i<N; i++){

    cin >> vec[i];

  }

  for(int i=0; i<N; i++){

    int64_t x = vec[i];

    dp[i+1][x] = powmod(2,N-1);

    for(int j=0; j<N_MAX; j++){

      dp[i+1][j] += dp[i][j]; //加えない

      if(j + x < N_MAX){ //加える

        int64_t y = dp[i][j];

        y %= MOD;

        y = y*modinv((int64_t)2,MOD) %MOD;

        dp[i+1][j+x] += y;

        dp[i+1][j+x] %= MOD;

      }

      dp[i+1][j] %= MOD;

    }

  }

  cout << (dp[N][S]) %MOD << endl;

}

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

using namespace std;



int64_t MOD = 998244353;



int64_t N_MAX = 3010;



int64_t dp[3010][3010];



//modの割り算

// a/bをa*modint(b,MOD) %MODに変換

long long modinv(long long a, long long m) {

  long long b = m, u = 1, v = 0;

  while (b) {

    long long t = a / b;

    a -= t * b; swap(a, b);

    u -= t * v; swap(u, v);

  }

  u %= m;

  if (u < 0) u += m;

  return u;

}



//繰り返し二乗法

int64_t powmod(int64_t x, int64_t n) { 

  int64_t ans = 1;

  while (n > 0) {

    if ((n & 1) == 1) {

      ans = ans * x;

      ans %= MOD;

    }

    x = x * x;//一周する度にx, x^2, x^4, x^8となる

    x %= MOD;

    n >>= 1; //桁をずらす n = n >> 1

  }

  return ans;

}



int main(){

  int N, S;

  cin >> N >> S;

  vector<int> vec(N);

  for(int i=0; i<N; i++){

    cin >> vec[i];

  }

  for(int i=0; i<N; i++){

    int x = vec[i];

    dp[i+1][x] = powmod(2,N-1);

    for(int j=0; j<N_MAX; j++){

      dp[i+1][j] += dp[i][j];

      if(j + x < N_MAX){

        int64_t y = dp[i][j];

        y = (y*modinv(2,MOD)) %MOD;

        dp[i+1][j+x] += y;

      }

      dp[i+1][j] %= MOD;

    }

  }

  cout << dp[N][S] << endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#pragma gcc optimize ("O2")

#pragma gcc optimize ("unroll-loops")



#include <bits/stdc++.h>





#define fi first

#define se second

#define pb(a) push_back(a)

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

#define el '\n'



using namespace std;

using ll = long long;

using pii = pair<int, int>;



const int N = 1e5 + 10;

const ll MOD = 1e9 + 7;



int n, k;

ll cnt[N];

vector<int> fac[N];



ll fpow(ll a, ll b){

    ll ret = 1;

    while (b){

        if (b & 1){

            ret = ret * a % MOD;

        }

        a = a * a % MOD;

        b >>= 1;

    }

    return ret;

}



int main () {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);



    cin >> n >> k;

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

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

            fac[j].pb(i);

        }

    }

    ll ans = 0;

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

        ll bag = k / i;

        ll temp = fpow(bag, n);

        cnt[i] = (cnt[i] + temp + MOD) % MOD;

        ans = (ans + cnt[i] * i) % MOD;



        for (auto x : fac[i]){

            cnt[x] = (cnt[x] - cnt[i] + MOD) % MOD;

        }

    }

    cout << ans << el;



    return 0;

}

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

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long ll;

ll n,k,ans;

ll sum[1000005],mod=1000000007ll;

ll pow1(ll x,ll y){

	ll a=1,b=x;while(y){if(y&1)a=(a*b)%mod;b=(b*b)%mod;y>>=1;}return a;

}

int main(){

    cin>>n>>k;

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

		sum[i]=pow1(k/i,n);

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

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

		}

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

	}

	cout<<ans;

	//system("pause");

    return 0;

}


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



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

#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)

#define rep1(i,n) for(int i = 1; i <= (n); i++)

#define rrep1(i,n) for(int i = (n); i > 0; i--)



#define ll long long

#define pi pair<int, int>

#define pll pair<ll, ll>



#define MOD 1000000007

#define INF 1000000000000000LL



using namespace std;



#define MAXKN 100001



bool is_prime[MAXKN];



// x^n in mod

ll modpow(ll x, ll n, ll mod){

  if(n==0) return 1;



  if(n%2==0){

    return modpow(x*x%mod, n/2, mod) % mod;

  }else{

    return x * modpow(x, (n-1), mod) % mod;

  }

}



int main(){

  ll n, k;cin>>n>>k;

  rep(i, MAXKN)is_prime[i]=true;

  is_prime[0]=is_prime[1]=false;

  for(int i=2; i<MAXKN; i++){

    for(int j=i*2; j<MAXKN; j+=i)is_prime[j]=false;

  }



  ll no1_count = 0;

  ll result = 0;



  ll one_count = modpow(k, n, MOD);

  vector<ll> counts;

  counts.push_back(0);

  rep1(a, k) counts.push_back( modpow(k/a, n, MOD) );



  rrep1(a, k){

    for(int i=a*2; i<=k; i+=a) counts[a]=(counts[a]-counts[i]+MOD)%MOD;

    result += a*counts[a];

    result %= MOD;

  }



  cout<<result<<endl;



  return 0;

}




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



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

#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)

#define rep1(i,n) for(int i = 1; i <= (n); i++)

#define rrep1(i,n) for(int i = (n); i > 0; i--)



#define ll long long

#define pi pair<int, int>

#define pll pair<ll, ll>



#define MOD 1000000007

#define INF 1000000000000000LL



using namespace std;



#define MAXKN 100001



// x^n in mod

ll modpow(ll x, ll n, ll mod){

  if(n==0) return 1;



  if(n%2==0){

    return modpow(x*x%mod, n/2, mod) % mod;

  }else{

    return x * modpow(x, (n-1), mod) % mod;

  }

}



int main(){

  ll n, k;cin>>n>>k;



  ll result = 0;

  vector<ll> counts(1);

  rep1(a, k) counts.push_back( modpow(k/a, n, MOD) );



  rrep1(a, k){

    for(int i=a*2; i<=k; i+=a) counts[a]=(counts[a]-counts[i]+MOD)%MOD;

    result += a*counts[a];

    result %= MOD;

  }



  cout<<result<<endl;



  return 0;

}




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



using namespace std;



const long long int MOD = 1e9 + 7;



vector <long long int> prime;



long long int mypow(long long int x,long long int n)

{

	long long int res = 1;

	while(n>0)

	{

		if(n%2==1)

		{

			res = ((res%MOD)*(x%MOD)%MOD);

			res%=MOD;

		}

		x = ((x%MOD)*(x%MOD)%MOD);

		x%=MOD;

		n/=2;

	}

	return res;

}



void eratos(void)

{

	bool isprime[100001];

	memset(isprime,true,sizeof(isprime));

	for(int i=2;i<=100000;i++)

	{

		if(isprime[i])

		{

			prime.push_back(i);

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

			{

				isprime[j] = false;

			}

		}

	}

}



long long int phi(long long int a)

{

	map <long long int,long long int> cnt;

	long long int tot = 1;

	for(int j=0;j<prime.size();j++)

	{

		if(a==1)

		{

			break;

		}

		while(1)

		{

			if(a%prime[j]!=0)

			{

				break;

			}

			a/=prime[j];

			cnt[prime[j]]++;

		}

	}

	if(a!=1)

	{

		cnt[a]++;

	}

	for(auto it : cnt)

	{

		long long int val = mypow(it.first,it.second) - mypow(it.first,it.second-1);

		val%=MOD;

		if(val < 0)

		{

			val += MOD;

		}

		tot*=val;

		tot%=MOD;

	}

	return tot;	

}

int main(void)

{

	cin.tie(0);

	ios::sync_with_stdio(false);



	long long int k,n;



	cin >> n >> k;



	eratos();



	long long int res = 0;



	for(long long int g=k;g>=1;g--)

	{

		long long int num = mypow(k/g,n);

		num = ((num%MOD)*(phi(g)%MOD)%MOD);

		res = ((res%MOD) + (num%MOD)%MOD);

		res%=MOD;

	}



	cout << res << '\n';



	return 0;

}

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



using namespace std;



const long long int MOD = 1e9 + 7;

long long int mypow(long long int x,long long int n)

{

	long long int res = 1;

	while(n > 0)

	{

		if(n%2==1)

		{

			res = ((res%MOD) * (x%MOD)%MOD);

			res%=MOD;

		}

		x = ((x%MOD)*(x%MOD)%MOD);

		x%=MOD;

		n/=2;

	}

	return res;

}

long long int dp[100001];



int main(void)

{

	cin.tie(0);

	ios::sync_with_stdio(false);



	int n,k;



	cin >> k >> n;



	long long int res = 0;

	

	for(int i=n;i>=1;i--)

	{

		dp[i] = mypow(n/i,k);

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

		{

			dp[i] -= dp[j];

			if(dp[i] < 0)

			{

				dp[i] += MOD;

			}

		}

		res = ((res%MOD) + ((i%MOD)*(dp[i]%MOD)%MOD)%MOD);

		res%=MOD;

	}



	cout << res << '\n';



	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//abc162_e.cpp

//Sun Apr 12 20:58:02 2020



#include <iostream>

#include <string>

#include <queue>

#include <map>

#include <unordered_map>

#include <vector>

#include <algorithm>

#include <math.h>

#include <set>

#define INTINF 2147483647

#define LLINF 9223372036854775807

#define MOD 1000000007



using namespace std;

using ll=long long;

typedef pair<int,int> P;



ll mod_pow(ll x, ll n, ll mod){

	if (n==0){

		return 1;

	}

	ll res = mod_pow(x*x%mod,n/2,mod);

	if (n&1){

		res = res * x % mod; //nが奇数の場合はxを余分にかける。

	}

	return res;

}



int main(){

	ll n,k;

	cin >> n >> k;



	ll njou[100010];

	njou[0] = 0;

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

		njou[i] = mod_pow(i,n,MOD);

	}



	ll ans = njou[k];

	ll counted = 0;

	ll counts[100010];

	fill(counts,counts+100010,0);

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

		ll yakusu = k/i;

		ll tmp = njou[yakusu];

		if (yakusu>=2){

			for (int j=2;j<=yakusu;j++){

				tmp = ((tmp-counts[i*j])%MOD+MOD)%MOD;

			}

		}

		ll tmp2 = (tmp * (i-1)) % MOD;

		ans = (ans+tmp2)%MOD;

		counted = (counted+tmp)%MOD;

		counts[i]=tmp;

	}



	cout << ans << endl;

//	ll modify = ((njou[k]-counted)%MOD+MOD)%MOD;

//	ans = (ans + modify)%MOD;

//	cout << njou[k] << endl;

//	cout << modify << endl;

//	cout << ans << endl;

}

// Optimized solution to the same problem (faster):
//abc162_e.cpp

//Thu May 14 21:30:18 2020



#include <iostream>

#include <string>

#include <queue>

#include <map>

#include <unordered_map>

#include <vector>

#include <algorithm>

#include <math.h>

#include <set>

#define INTINF 2147483647

#define LLINF 9223372036854775807

#define MOD 1000000007



using namespace std;

using ll=long long;

typedef pair<int,int> P;



ll mod_pow(ll x, ll n){

	ll res = 1;

	while (n>0){

		if (n&1){

			res = res * x % MOD;

		}

		x = x*x%MOD;

		n >>= 1;

	}

	return res;

}



int main(){

	ll n,k;

	cin >> n >> k;



	ll ans = 0;

	ll comb[k+1];

	fill(comb,comb+k+1,0);

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

		ll baisu = k/i;

		comb[i] = mod_pow(baisu,n);

		for (int j=2;j<=baisu;j++){

			comb[i] = (comb[i]-comb[i*j]+MOD)%MOD;

		}

		ans = (ans + comb[i]*i)%MOD;

	}



	cout << ans << endl;



}

// Fastest known solution for this problem: