#include //using namespace std; #pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define rep(i,j,n) for(ll i=(ll)(j);i<(ll)(n);i++) #define REP(i,j,n) for(ll i=(ll)(j);i<=(ll)(n);i++) #define per(i,j,n) for(ll i=(ll)(j);(ll)(n)<=i;i--) #define ll long long #define ALL(a) (a).begin(),(a).end() #define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(ll)(key))) #define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(ll)(key))) #define pb emplace_back #define mp std::make_pair // #define endl "\n" //using std::endl; using std::cin; using std::cout; using std::vector; using std::string; using std::upper_bound; using std::lower_bound; using vi=vector; using vii=vector; using pii=std::pair; // constexpr ll MOD=1e9+7; //constexpr ll MOD=998244353; //constexpr ll MOD=10000000; //constexpr ll MOD=1e4; //constexpr ll MOD=1e5; constexpr ll MAX=3e6; constexpr ll inf=(1ll<<60); template class prique :public std::priority_queue, std::greater> {}; template struct Segment_tree{ ll N; T mem; vector node; Segment_tree(vector &X,T m):mem(m){ ll sz=X.size(); N=1; while(N0){ X=(X-1)/2; node[X]=Compare(node[X*2+1],node[X*2+2]); } } T Query(ll a,ll b,ll now=0,ll l=0,ll r=-1){ //[a,b),[l,r) if(r<0) r=N; if(r<=a||b<=l) return mem; if(a<=l&&r<=b) return node[now]; auto vl=Query(a,b,now*2+1,l,(l+r)/2),vr=Query(a,b,now*2+2,(l+r)/2,r); return Compare(vl,vr); } ll lower_bound(ll left,ll right,T val,ll now=0,ll l=0,ll r=-1){ if(r<0) r=N; if(node[now]=right||left>=r) return r; else if(now>=N-1) return l; ll vl=lower_bound(left,right,val,now*2+1,l,(l+r)/2); if(vl==(l+r)/2) return lower_bound(left,right,val,now*2+2,(l+r)/2,r); return vl; } }; template struct lazy_Segment_tree{ int N; vector node,lazy; T INF; vector flag; lazy_Segment_tree(vector X,T Y):INF(Y){ N=1; while(X.size()>N) N*=2; node.resize(2*N-1,Y); lazy.resize(2*N-1); flag.resize(2*N-1); rep(i,0,X.size()) node[i+N-1]=X[i]; per(i,N-2,0) node[i]=compare(node[i*2+1],node[i*2+2]); } T compare(T X,T Y){ return std::max(X,Y); } T plus(T X,int l,int r){ return X; } void eval(int now,int l,int r){ if(flag[now]){ if(r-l>1){ flag[now*2+1]=flag[now*2+2]=1; lazy[now*2+1]=lazy[now*2+2]=lazy[now]; } node[now]=lazy[now]; flag[now]=0; } } void update(int a,int b,T add,int now=0,int l=0,int r=-1){ if(r<0) r=N; eval(now,l,r); if(b<=l||r<=a) return; if(a<=l&&r<=b){ lazy[now]=add; flag[now]=1; eval(now,l,r); } else{ update(a,b,add,now*2+1,l,(r+l)/2); update(a,b,add,now*2+2,(r+l)/2,r); node[now]=compare(node[now*2+1],node[now*2+2]); } } T Query(int a,int b,int now=0,int l=0,int r=-1){ if(r<0) r=N; eval(now,l,r); if(b<=l||r<=a) return INF; if(a<=l&&r<=b) return node[now]; return compare(Query(a,b,now*2+1,l,(r+l)/2),Query(a,b,now*2+2,(r+l)/2,r)); } ll lower_bound(ll left,ll right,T val,ll now=0,ll l=0,ll r=-1){ eval(now,l,r); if(r<0) r=N; if(node[now]=right||left>=r) return r; else if(now>=N-1) return l; ll vl=lower_bound(left,right,val,now*2+1,l,(l+r)/2); if(vl==(l+r)/2) return lower_bound(left,right,val,now*2+2,(l+r)/2,r); return vl; } }; struct Binary_indexed_tree{ int N; vi bit; Binary_indexed_tree(int n):N(n){ bit.resize(N+1,0); } void add(int x,ll a){ x++; for(x;x<=N;x+=(x&-x)) bit[x]+=a; } ll sum(int x){ x++; ll ret=0; for(x;x>0;x-=(x&-x)) ret+=bit[x]; return ret; } ll lower_bound(ll X){ if(sum(N)0){ if(memo+ret<=N&&sum+bit[memo+ret] seen(n); ll cnt=0; rep(i,0,n){ if(num[i]==-1){ dfs(i,e,num,cnt); } } rep(i,0,n) po[num[i]]=i; per(i,n-1,0){ ll X=po[i]; if(!seen[X]){ std::queue que; vi v; que.push(X); seen[X]=1; while(!que.empty()){ ll now=que.front(); que.pop(); v.pb(now); ind[now]=ver.size(); for(auto p:revedge[now]){ if(!seen[p]){ seen[p]=1; que.push(p); } } } ver.pb(v); } } N=ver.size(); M=0; edge.resize(N); rep(i,0,n){ for(auto p:e[i]){ if(ind[i]==ind[p]) continue; M++; edge[ind[i]].pb(ind[p]); } } } void dfs(ll now,vii &e,vi &num,ll &cnt){ num[now]=0; for(auto next:e[now]){ if(num[next]==-1){ dfs(next,e,num,cnt); } } num[now]=cnt++; } }; struct lowlink{ ll N; vii edge; vi ord,low,aps; vector used; vector bridges; lowlink(vii e):edge(e){ N=edge.size(); used.resize(N); ord.resize(N); low.resize(N); ll cnt=0; rep(i,0,N){ if(!used[i]) dfs(i,cnt,-1); } } void dfs(ll now,ll &cnt,ll from){ used[now]=1; ord[now]=cnt++; low[now]=ord[now]; bool flag=0; for(auto next:edge[now]){ if(!used[now]){ dfs(next,cnt,now); low[now]=std::min(low[now],low[next]); if(from!=-1&&ord[now]<=low[next]) flag=1; if(ord[now]=2) flag=1; if(flag) aps.pb(now); } }; struct Directed_Gragh{ ll N,M; vii edge; Directed_Gragh(vii e):edge(e){ N=edge.size(); rep(i,0,N) M+=edge[i].size(); } vi sort(){ vi ret; vi cnt(N); rep(i,0,N){ for(auto p:edge[i]) cnt[p]++; } std::queue que; rep(i,0,N){ if(cnt[i]==0) que.push(i); } while(!que.empty()){ ll now=que.front(); que.pop(); ret.pb(now); for(auto next:edge[now]){ cnt[next]--; if(cnt[next]==0) que.push(next); } } return ret; } }; struct Tree{ int N; vii dp; vi par; vi dist; vi subtree; vii edge; Tree(vii E):edge(E){ N=edge.size(); dp.resize(N); par.resize(N); dist.resize(N,-1); for(int i=0;i que; que.push(0); while(!que.empty()){ int now=que.front(); que.pop(); for(int i=0;i=0;i--){ if(dp[X][i]!=dp[Y][i]){ X=dp[X][i]; Y=dp[Y][i]; } } return dp[X][0]; } void Subtree(){ subtree.resize(N,-1); dfs(0); } void dfs(ll now){ subtree[now]=1; for(auto next:edge[now]){ if(subtree[next]==-1){ dfs(next); subtree[now]+=subtree[next]; } } } }; template struct tancomp{ int place(std::pair p){ if(p.first<=0&&p.second<0) return 0; if(p.first>0&&p.second<=0) return 1; if(p.first==0&&p.second==0) return 2; if(p.first>=0&&p.second>0) return 3; return 4; } bool operator()(const std::pair &l,const std::pair &r){ if(place(l)!=place(r)) return place(l) vector> Declination_sort(ll N,vector X,vector Y){ vector> ret(N); rep(i,0,N){ ret[i]=(mp(X[i],Y[i])); } sort(ALL(ret),tancomp()); return ret; } long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } vi fac,finv,inv; void COMinit() { fac.resize(MAX); finv.resize(MAX); inv.resize(MAX); fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } ll COM(ll n,ll r){ if(n memo; rep(i,0,A.size()) memo[A[i]]=0; ll cnt=0; for(auto &p:memo) p.second=cnt++; rep(i,0,A.size()) A[i]=memo[A[i]]; } void dec(std::map &mem,ll X){ mem[X]--; if(mem[X]==0) mem.erase(X); } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::random_device rnd; std::mt19937 mt(rnd()); ll N,M; cin>>N>>M; REP(i,1,M){ ll X=N/i; ll ans=modpow(X+1,N%i,MOD)*modpow(X,i-N%i,MOD)%MOD; if(i>1&&N%i==0){ ans=modpow(X,N-2,MOD)*(X+1)%MOD*(X-1)%MOD; } if(X==1&&N%i