#include<bits/stdc++.h> #include<unordered_set> #include<unordered_map> using namespace std; #define int long long #define REP(i,m,n) for(int i=(m);i<(n);i++) #define rep(i,n) REP(i,0,n) #define pb push_back #define all(a) a.begin(),a.end() #define rall(c) (c).rbegin(),(c).rend() #define mp make_pair #define endl '\n' typedef long long ll; typedef pair<ll,ll> pll; typedef long double ld; const ll inf=1e9+7; const ll mod=1e9+7; signed main(){ ll m,K;cin>>m>>K; vector<vector<vector<ll> > > nxt(34,vector<vector<ll> >(m,vector<ll>(m))); rep(i,34){ rep(j,m){ rep(k,m){ if(i==0){ nxt[i][j][(j+k)%m]++; nxt[i][j][j*k%m]++; }else{ rep(l,m){ nxt[i][j][k]=(nxt[i][j][k]+nxt[i-1][j][l]%mod*nxt[i-1][l][k])%mod; } } } } } vector<ll>dp(m); vector<ll>dp1(m); dp[0]=1; rep(i,34){ if((1LL<<i)&K){ rep(j,m){ rep(k,m){ dp1[k]=(dp1[k]+dp[j]*nxt[i][j][k]%mod)%mod; } } rep(j,m){ dp[j]=dp1[j]; dp1[j]=0; } } } cout<<dp[0]<<endl; }