#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; using ll=long long; const ll LNF=1e18; const int INF = 1e9+1; const ll M = 1e9+7;
typedef pair<int,int> P;

struct mat {
  vector<vector<ll>> v, v2;
  vector<ll> an, an2; int n;
  mat(int _n) : n(_n) {
    v.resize(n);
    for(int i=0;i<n;i++) v[i].resize(n);
    v2.resize(n);
    for(int i=0;i<n;i++) v2[i].resize(n);
    an.resize(n); an2.resize(n);
  }
  void initialize() {
    // 各自で調整
    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
        v[i][j]++;
      }
    }
    
    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
        v[i][i*j%n]++;
      }
    }

    an[0]=1;
  }
  void update() {
    //cout << "Updating...";
    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++)
        v2[i][j]=0;
      //v2[i].assign(n, 0LL);
    }

    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
        for(int k=0;k<n;k++) {
          v2[i][j] += v[i][k] * v[k][j] % M;
        }
        v2[i][j] %= M;
      }
    }

    v=v2;
    //cout << "Done!" << endl;
  }
  void update_ans() {
    //an2.assign(n, 0LL);
    for(int i=0;i<n;i++) {
      an2[i]=0;
    }
    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
        an2[i] += v[i][j] * an[j] % M;
      }
      an2[i] %= M;
    }
    an=an2;
  }
  void solve(ll x) {
    // x乗
    while(x>0) {
      if (x&1) update_ans();
      update();
      x>>=1;
    }
  }

  void print() {
    for(int i=0;i<n;i++) {
      for(int j=0;j<n;j++) {
        cout << v[i][j]<<" ";
      } cout << endl;
    }

    for(int i=0;i<n;i++) {
      cout<<an[i]<<" ";
    } cout<<endl<<endl;
  }
};

int main() {
  ll m,k; cin>>m>>k;
  mat ma(m);
  ma.initialize();
  //ma.print();
  ma.solve(k);
  //ma.print();
  cout<<ma.an[0]<<endl;
}