Consider sequences \\{A_1,...,A_N\\} of length N consisting of integers between 1 and K (inclusive).

There are K^N such sequences. Find the sum of \gcd(A_1, ..., A_N) over all of them.

Since this sum can be enormous, print the value modulo (10^9+7).

Here \gcd(A_1, ..., A_N) denotes the greatest common divisor of A_1, ..., A_N.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq K \leq 10^5
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K


Output

Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7).

Examples

Input

3 2


Output

9


Input

3 200


Output

10813692


Input

100000 100000


Output

742202979
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD=1e9+7;

ll mod_pow(ll x, ll n){ //べき乗
    ll ans=1;
    x%=MOD;
    while(n!=0){
        if(n&1) ans=ans*x%MOD;
        x=x*x%MOD;
        n=n>>1;
    }
    return ans%MOD;
}

int main(){
    int N,K; cin >> N >> K;
    ll ans=0;
    map<int,ll> ma;
    for(int i=K;i>=1;i--){
        int tmp=K/i;
        ll res=mod_pow(tmp,N);
        for(int j=2;j<=tmp;j++){
            ll k=i*j;
            res=(res-ma[k]+MOD)%MOD;
        }
        ma[i]=res;
        ans+=(res*i)%MOD;
        ans%=MOD;
    }
    cout << ans << endl;
}