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

#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i =(j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
typedef long long ll;
const ll INFF = (ll)1e18;
const int INF = (int)1e9;
ll k, n;
const ll mod = (int)1e9 + 7;
vector<vector<ll>> mul(vector<vector<ll>> a, vector<vector<ll>> b){
    vector<vector<ll>> mat(k, vector<ll>(k, 0));
    REP(i, k){
        REP(j, k){
            REP(g, k){
                mat[i][j] += a[i][g] * b[g][j];
                mat[i][j] %= mod;
            }
        }
    }
    return mat;
}
vector<vector<ll>> binpow(vector<vector<ll>> a, ll y){
    vector<vector<ll>> res(k, vector<ll>(k, 0));
    REP(i, k) res[i][i] = 1;
    while(y > 0){
        if(y&1){
            res = mul(res, a);
        }
        y>>=1;
        a = mul(a, a);
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> k >> n;
    vector<vector<ll>> in(k, vector<ll>(k, 0));
    REP(i, k){
        REP(j, k){
            int f = i + 1; int s = j + 1;
            if(__gcd(f, s) == 1){
                in[i][j] = 1;
            }
        }
    }
    /*
    REP(i, k){
        REP(j, k){
            cout << in[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "---\n";
    REP(i, k){
        REP(j, k){
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }
    */
    vector<vector<ll>> ans = binpow(in, n - 1);
    
    ll result = 0;
    REP(i, k){
        REP(j, k){
            result += ans[i][j];
            result %= mod;
        }
    }
    cout << result << "\n";
    return 0;
}