#include using namespace std; #define rep(i,n) REP(i,0,n) #define REP(i,s,e) for(int i=(s); i<(int)(e); i++) #define repr(i, n) REPR(i, n, 0) #define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--) #define all(r) r.begin(),r.end() #define rall(r) r.rbegin(),r.rend() typedef long long ll; typedef vector vi; typedef vector vl; const ll INF = 1e18; const ll MOD = 1e9 + 7; template T chmax(T& a, const T& b){return a = (a > b ? a : b);} template T chmin(T& a, const T& b){return a = (a < b ? a : b);} template struct Mat { array, SZ> d; const int n; Mat() : n(SZ) { array tmp; d.fill(tmp); } Mat operator * (const Mat& mt) const { Mat ret; rep(i, SZ) rep(j, SZ) { rep(k, SZ) { ret.d[i][j] += (d[i][k] * mt.d[k][j]); } } return ret; } Mat& operator *= (const Mat& mt) { *this = *this * mt; return *this; } Mat& operator = (const Mat& mt) { d = mt.d; return *this; } array& operator [](const int n) { return d[n]; } }; template Mat pow(Mat mt, ll n) { Mat ret; rep(i, SZ) ret.d[i][i] = 1LL; while(n > 0) { if(n&1LL) ret = ret * mt; mt = mt*mt; n >>= 1; } return ret; } template T pow_fast(T x, U n) { T ret = (T)1; while(n) { if(n & (U)1) ret *= x; x *= x; n >>= 1; } return ret; } template struct ModInt { ModType val; ModInt() : val(0) {} ModInt(ModType x) : val(x % MOD) { if(val < 0) val += MOD; }; operator ModType() const { return val; } ModInt &operator+=(const ModInt &m) { val += m.val; if(val >= MOD) val -= MOD; return *this; } ModInt &operator-=(const ModInt &m) { val -= m.val; if(val < 0) val += MOD; return *this; } ModInt &operator*=(const ModInt &m) { (val *= m.val) %= MOD; return *this; } ModInt &operator/=(const ModInt &m) { *this *= m.inverse(); return *this; } ModInt operator+(const ModInt &m) const { return ModInt(*this) += m; } ModInt operator-(const ModInt &m) const { return ModInt(*this) -= m; } ModInt operator*(const ModInt &m) const { return ModInt(*this) *= m; } ModInt operator/(const ModInt &m) const { return ModInt(*this) /= m; } ModInt inverse() const { return pow_fast(*this, MOD - 2); } ModInt pow(ModType n) const {return pow_fast(*this, n); } friend std::ostream &operator<<(std::ostream &os, const ModInt &rhs) { os << rhs.val; return os; } friend std::istream &operator>>(std::istream &is, ModInt &rhs) { ModType value; is >> value; rhs = ModInt(value); return is; } }; using mint = ModInt; int main(){ int m, k; cin >> m >> k; Mat mt; rep(i, m) rep(j, m) { mt[i][(i+j)%m] += mint(1); mt[i][(i*j)%m] += mint(1); } auto d = pow(mt, k); cout << d[0][0] << '\n'; return 0; }