#include #include using namespace std; using ll=long long; #define rep(i,n) for(int i=0;i<(n);++i) vector> make_mat(vector v){ if(v.empty())return vector>(1,vector()); long long n=v.back(); v.pop_back(); vector> ret; vector> tmp=make_mat(v); for(auto e:tmp)for(long long i=0;i 1) ret -= ret / n; return ret; } int main(){ ll m,d,n,b; cin>>m>>d>>n>>b; vectorphi=vector{b}; while(phi.back()!=1){ phi.emplace_back(euler_phi(phi.back())); } auto mul=[&](vectorv){ vectorres(phi.size()); rep(i,phi.size()-1){ ll tmp=1,k=v[i]+d; if(k>=phi[i]*2)k=k%phi[i]+phi[i]; bool over=0; rep(j,v[i+1]){ tmp*=k; if(tmp>=phi[i]*2)tmp=tmp%phi[i]+phi[i]; } res[i]=tmp; } res.back()=1; return res; }; auto tb=phi; rep(i,phi.size())tb[i]*=2; map,vector>ma; for(auto v:make_mat(tb)){ ma[v]=mul(v); } vectorv(phi.size()); rep(i,phi.size()){ v[i]=m%phi[i]+(m>=phi[i]?phi[i]:0); } auto ans=v; // cerr<,vector>ma2; for(auto [s,t]:ma){ ma2[s]=mul(t); } n/=2; swap(ma,ma2); } if(ans[0]%b==10)cout<<"A"<