#include <bits/stdc++.h>

const int N = 1e4 + 7;


using namespace std;

#define FOR(a, b, c) for(int a = b; a < c; a++)
const int MOD = 1e9 + 7;

struct matrix {
	vector<vector<int>> a;
	int n, m;
	
	matrix(int n, int m) : n(n), m(m) {
		a.resize(n, vector<int>(m, 0));
	}
	
	matrix operator+(const matrix& o) {
		matrix res(n, m);
		FOR(i, 0, n) FOR(j, 0, m) {
			res.a[i][j] = (a[i][j] + o.a[i][j]) % MOD;
		}
		return res;
	}
	
	matrix operator*(const matrix& o) {
		matrix res(n, o.m);
		FOR(i, 0, n) FOR(k, 0, o.m) FOR(j, 0, m) {
			res.a[i][k] = (res.a[i][k] + 1ll * a[i][j] * o.a[j][k]) % MOD;
		}
		return res;
	}
	
	matrix operator^(long long k) {
		matrix res(n, n), a{*this};
		FOR(i, 0, n) res.a[i][i] = 1;
		
		for (; k; k >>=1) {
			if (k & 1) res = res * a;
			a = a * a;
		}
		
		return res;
	}
};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int k;
	long long n;
	cin >> k >> n;
	
	matrix mat(k, k);
	
	FOR(i, 0, k) FOR(j, 0, k) {
		mat.a[i][j] = __gcd(i + 1, j + 1) == 1;
	}
	
	auto xd = mat ^ n;
	
	int res = 0;
	
	FOR(i, 0, k) {
		res = (res + xd.a[0][i]) % MOD;
	}
		
	cout << res << "\n";
	
}