#include #define rep(i,n) for (int i = 0; i < (n); ++i) #define rrep(i,n) for (int i = (n)-1; i >= 0; i--) #define rep2(i,s,n) for (int i = (s); i < (n); ++i) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define pb push_back #define eb emplace_back #define vi vector #define vvi vector> #define vl vector #define vvl vector> #define vs vector #define vc vector #define vb vector #define vp vector

using namespace std; using ll = long long; using P = pair; using LP = pair; template istream& operator>>(istream& is,vector& v) { for(T& t:v){is>>t;} return is; } template ostream& operator<<(ostream& os,const vector& v) { for(T t:v){os< inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;} template inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;} const int inf = 1001001001; const ll linf = 1001001001001001001; const int mod = 1000000007; //const int mod = 998244353; struct mint { ll x; explicit mint(ll x=0):x((x%mod+mod)%mod){} mint operator-() const { return mint(-x);} mint& operator+=(const mint& a) { if ((x += a.x) >= mod) x -= mod; return *this;} mint& operator++(int n) { return *this += mint(1); } mint& operator-=(const mint& a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator--(int n) { return *this -= mint(1); } mint& operator*=(const mint& a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint& a) const { mint res(*this); return res+=a; } mint operator-(const mint& a) const { mint res(*this); return res-=a; } mint operator*(const mint& a) const { mint res(*this); return res*=a; } bool operator==(const int& n) const { mint a(n); return this->x == a.x; } bool operator==(const ll& n) const { mint a(n); return this->x == a.x; } bool operator!=(const int& n) const { mint a(n); return this->x != a.x; } bool operator!=(const ll& n) const { mint a(n); return this->x != a.x; } mint pow(ll t) const { mint res = mint(1),a(*this); while(t > 0) { if(t&1) res *= a; t >>= 1; a *= a; } return res; } // for prime mod mint inv() const { return pow(mod-2); } mint& operator/=(const mint& a) { return (*this) *= a.inv(); } mint operator/(const mint& a) const { mint res(*this); return res/=a; } }; ostream& operator<<(ostream& os,const mint& m) { return os << m.x; } template struct matrix { int h,w; vector> v; matrix(int h,int w,T t):h(h),w(w),v(vector>(h,vector(w,t))) {} matrix(vector> v):v(v),h(v.size()),w(v[0].size()) {} matrix& operator+=(const matrix& a) { rep(i,h) rep(j,w) v[i][j] += a.v[i][j]; return *this; } matrix& operator*=(const int& k) { rep(i,h) rep(j,w) v[i][j] *= k; return *this; } matrix& operator-=(const matrix& a) { *this += a*(-1); return *this; } matrix operator+(const matrix& a) const { return res(*this) += a; } matrix operator*(const int& k) const { return res(*this) *= k; } matrix operator-(const matrix& a) const { return res(*this) -= a; } matrix operator*(const matrix& a) const { matrix res(h,a.w,T(0)); rep(i,h) rep(j,a.h) rep(k,a.w) res.v[i][k] += v[i][j]*a.v[j][k]; return res; } matrix& operator*=(const matrix& a) { return *this = *this*a; } matrix pow(ll t) const { matrix res(h,w,T(0)),a(*this); rep(i,h) res.v[i][i] = T(1); while(t > 0) { if(t&1) res *= a; t >>= 1; a *= a; } return res; } vector& operator[](int x) { return v[x]; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int m,k; cin >> m >> k; vector> v(m,vector(m,mint(0))); rep(i,m) { rep(j,m) { int n1 = (i+j)%m,n2 = i*j%m; v[n1][i]++; v[n2][i]++; } } vector> u(m,vector(1,mint(0))); u[0][0] = mint(1); matrix V(v),U(u); matrix ans = V.pow(k)*U; cout << ans[0][0] << endl; }