#define MOD_TYPE 998244353 // #define MOD_TYPE 1000000007 // #define EXPAND // #define MOD_EXPAND #pragma region Macros #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("O3,unroll-loops") #include using namespace std; using namespace std::literals; #if __has_include() || defined(EXPAND) #include #include #include #include #include #include #include #include #include #include using namespace atcoder; #endif using ll= long long; using ld= long double; using ull= unsigned long long; using i128= __int128; using u128= unsigned __int128; using str= std::string; using pll= std::pair; template using vec= std::vector; template< class T, class Container= vec, class Compare= std::less> using prique= std::priority_queue; using vi= vec; using vl= vec; using vd= vec; using vs= vec; using vi128= vec; using vpll= vec; using vvi= vec; using vvl= vec; using vvd= vec; using vvs= vec; using vvi128= vec; using vvpll= vec; #if __has_include() || defined(MOD_EXPAND) #if MOD_TYPE == 1000000007 using mint= atcoder::modint1000000007; #elif MOD_TYPE == 998244353 using mint= atcoder::modint998244353; #endif using vm= vec; using vvm= vec; #endif #if MOD_TYPE == 1000000007 constexpr ll mod= 1000000007ll; #elif MOD_TYPE == 998244353 constexpr ll mod= 998244353ll; #endif #define ALL(x) (x).begin(), (x).end() #define OVERLOAD3(_1, _2, _3, name, ...) name #define OVERLOAD5(_1, _2, _3, _4, _5, name, ...) name #define REPBASE(i, a, b) for(ll i= (a), i##_b= (b); i < i##_b; i++) #define RREPBASE(i, a, b) for(ll i= (a), i##_b= (b); i >= i##_b; i--) #define LOOP(n) REPBASE(i##__COUNTER__##_##__LINE__, 0, n) #define REPB(i, n) REPBASE(i, 0, n) #define REPS(i, n) REPBASE(i, 1, n + 1) #define RREP(i, n) RREPBASE(i, n - 1, 0) #define RREPS(i, n) RREPBASE(i, n, 1) #define REP(...) OVERLOAD3(__VA_ARGS__, REPBASE, REPB, LOOP)(__VA_ARGS__) #define EACH1(x, c) for(auto &&x: c) #define EACH2(x, y, c) for(auto &&[x, y]: c) #define EACH3(x, y, z, c) for(auto &&[x, y, z]: c) #define EACH4(x, y, z, w, c) for(auto &&[x, y, z, w]: c) #define EACH(...) OVERLOAD5(__VA_ARGS__, EACH4, EACH3, EACH2, EACH1)(__VA_ARGS__) #define PERM(p) \ std::sort(ALL(p)); \ for(bool(p##c)= true; (p##c); (p##c)= std::next_permutation(ALL(p))) #define eb emplace_back #define fi first #define se second #define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0) template struct is_pair : std::false_type {}; template struct is_pair> : std::true_type {}; template inline constexpr bool is_pair_v= is_pair::value; template struct is_tuple : std::false_type {}; template struct is_tuple> : std::true_type {}; template inline constexpr bool is_tuple_v= is_tuple::value; template inline constexpr bool has_iterator= false; template inline constexpr bool has_iterator> = true; template inline constexpr bool has_value_type= false; template inline constexpr bool has_value_type> = true; #if __has_include() || defined(MOD_EXPAND) template inline constexpr bool is_modint_v= atcoder::internal::is_modint::value; #endif template constexpr ll sz(const T &x) { return std::size(x); } constexpr ll topbit(const ll &t) { return (t == 0 ? -1 : 63 - __builtin_clzll(t)); } constexpr ll bit(const ll &n) noexcept { return (1ll << n); } template constexpr T div_ceil(const T &a, const U &b) { assert(b != 0); return (a < 0) == (b < 0) ? (a + b - (b > 0) + (b < 0)) / b : a / b; } template constexpr T div_floor(const T &a, const U &b) { assert(b != 0); return (a < 0) == (b < 0) ? a / b : (a - b + (b > 0) - (b < 0)) / b; } str YES(const bool &n) noexcept { return (n ? "YES"s : "NO"s); } str Yes(const bool &n) noexcept { return (n ? "Yes"s : "No"s); } str yes(const bool &n) noexcept { return (n ? "yes"s : "no"s); } template constexpr void uniq(T &v) { v.erase(std::unique(v.begin(), v.end()), v.end()); } template constexpr ll lb(const T &v, const U &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); } template constexpr ll lb(const T &v, const U &x, Compare comp) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x, comp)); } template constexpr ll ub(const T &v, const U &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); } template constexpr ll ub(const T &v, const U &x, Compare comp) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x, comp)); } template constexpr ll er(const T &v, const U &x, const V &y) { return std::distance( std::lower_bound(v.begin(), v.end(), x), std::upper_bound(v.begin(), v.end(), y)); } template constexpr ll er(const T &v, const U &x, const V &y, Compare comp) { return std::distance( std::lower_bound(v.begin(), v.end(), x, comp), std::upper_bound(v.begin(), v.end(), y, comp)); } template constexpr bool chmax(T &a, const U &b) noexcept { if(a < b) { a= b; return true; } return false; } template constexpr bool chmax(T &a, const U &b, Compare comp) noexcept { if(comp(a, b)) { a= b; return true; } return false; } template constexpr bool chmin(T &a, const U &b) noexcept { if(b < a) { a= b; return true; } return false; } template constexpr bool chmin(T &a, const U &b, Compare comp) noexcept { if(comp(b, a)) { a= b; return true; } return false; } template typename Container::value_type sum(Container &c) { return std::accumulate(c.begin(), c.end(), typename Container::value_type()); } constexpr std::array dx4{{{1ll, 0ll}, {0ll, 1ll}, {-1ll, 0ll}, {0ll, -1ll}}}; constexpr std::array dx8{ {{1ll, 0ll}, {1ll, 1ll}, {0ll, 1ll}, {-1ll, 1ll}, {-1ll, 0ll}, {-1ll, -1ll}, {0ll, -1ll}, {1ll, -1ll}}}; template struct rec { F f; rec(F &&f_) noexcept(noexcept(F(std::forward(f_)))) : f(std::forward(f_)) {} template auto operator()(Args &&...args) const noexcept(noexcept(f(*this, std::forward(args)...))) { return f(*this, std::forward(args)...); } }; template constexpr std::pair operator+(std::pair p, const std::pair &q) { p+= q; return p; } template constexpr std::pair &operator+=(std::pair &p, const std::pair &q) { p.first+= q.first; p.second+= q.second; return p; } template constexpr std::pair operator-(std::pair p, const std::pair &q) { p-= q; return p; } template constexpr std::pair &operator-=(std::pair &p, const std::pair &q) { p.first-= q.first; p.second-= q.second; return p; } template constexpr std::pair operator+(const std::pair &p) { return p; } template constexpr std::pair operator-(const std::pair &p) { return {-p.first, -p.second}; } inline i128 parse(str s) { std::reverse(s.begin(), s.end()); i128 ret= 0; bool minus= false; if(s.back() == '-') { minus= true; s.pop_back(); } while(!s.empty()) { if('0' <= s.back() && s.back() <= '9') { ret= ret * 10 + s.back() - '0'; s.pop_back(); } else { break; } } std::reverse(s.begin(), s.end()); if(minus) ret*= -1; return ret; } inline str to_string(i128 val) { str ret= ""s; bool minus= false; if(val < 0) { minus= true; val*= -1; } do { char digit= static_cast(48 + val % 10); ret+= digit; val/= 10; } while(val != 0); if(minus) ret+= "-"s; std::reverse(ret.begin(), ret.end()); return ret; } inline str to_string(u128 val) { str ret= ""s; do { char digit= static_cast(48 + val % 10); ret+= digit; val/= 10; } while(val != 0); std::reverse(ret.begin(), ret.end()); return ret; } #define CHR(...) \ char __VA_ARGS__; \ input(__VA_ARGS__) #define STR(...) \ str __VA_ARGS__; \ input(__VA_ARGS__) #define LL(...) \ ll __VA_ARGS__; \ input(__VA_ARGS__) #define LD(...) \ ld __VA_ARGS__; \ input(__VA_ARGS__) #define I128(...) \ i128 __VA_ARGS__; \ input(__VA_ARGS__) #define VEC(name, size, ...) \ vec<__VA_ARGS__> name(size); \ input(name) #define VV(name, h, w, ...) \ std::vector name((h), vec<__VA_ARGS__>(w)); \ input(name) #ifdef _WIN32 int inline getchar_unlocked() { return _getchar_nolock(); } void inline putc_unlocked(char c, FILE *stream) { _putc_nolock(c, stream); } #endif struct in { in()= delete; static inline void input_impl(char &a) { do { a= static_cast(getchar_unlocked()); } while(a == ' ' || a == '\n'); } static inline void input_impl(str &a) { a= ""s; int c; do { c= getchar_unlocked(); } while(c == ' ' || c == '\n'); do { a+= static_cast(c); c= getchar_unlocked(); } while(c != EOF && c != ' ' && c != '\n'); std::ungetc(c, stdin); } template< class T, std::enable_if_t< std::is_integral_v || std::is_same_v || std::is_same_v, std::nullptr_t> = nullptr> static inline void input_impl(T &a) { a= 0; int c; do { c= getchar_unlocked(); } while(c == ' ' || c == '\n'); bool minus= 0; if(c == '-') { minus= 1; c= getchar_unlocked(); } if(c < '0' || '9' < c) { std::ungetc(c, stdin); return; } do { (a*= 10)+= c - 48; c= getchar_unlocked(); } while('0' <= c && c <= '9'); std::ungetc(c, stdin); if(minus) a*= -1; } static inline void input_impl(float &a) { std::scanf("%f", &a); } static inline void input_impl(double &a) { std::scanf("%lf", &a); } static inline void input_impl(ld &a) { std::scanf("%Lf", &a); } template static inline void input_impl(std::pair &a) { input_impl(a.first); input_impl(a.second); } template, std::nullptr_t> = nullptr> static inline void input_impl(T &a) { if constexpr(std::tuple_size_v != 0) { input_impl_tuple_impl(a, std::make_index_sequence>()); } } template, std::nullptr_t> = nullptr> static inline void input_impl(T &a) { for(auto &&e: a) { input_impl(e); } } private: template static inline void input_impl_tuple_impl(T &A, std::index_sequence) { using swallow= std::initializer_list; swallow{(input_impl(std::get(A)), 0)...}; } }; template inline void input(Args &...args) { using swallow= std::initializer_list; swallow{(in::input_impl(args), 0)...}; } struct out { private: template> struct has_print_impl : std::false_type {}; template struct has_print_impl().print_impl(0))>> : std::true_type {}; template static constexpr bool has_print_impl_v= has_print_impl::value; public: out()= delete; static inline void print_impl(FILE *stream, const char *const &a) { std::fputs(a, stream); } template static inline void print_impl(FILE *stream, T *const &a) { std::fprintf(stream, "%p", a); } static inline void print_impl(FILE *stream, const char &a) { putc_unlocked(a, stream); } static inline void print_impl(FILE *stream, const str &a) { std::fputs(a.c_str(), stream); } template static inline void print_impl(FILE *stream, const char (&a)[length]) { std::fputs(a, stream); } static inline void print_impl(FILE *stream, const bool &a) { putc_unlocked('0' + a, stream); } static inline void print_impl(FILE *stream, const signed char &a) { std::fprintf(stream, "%hhd", a); } static inline void print_impl(FILE *stream, const short &a) { std::fprintf(stream, "%hd", a); } static inline void print_impl(FILE *stream, const int &a) { std::fprintf(stream, "%d", a); } static inline void print_impl(FILE *stream, const long &a) { std::fprintf(stream, "%ld", a); } static inline void print_impl(FILE *stream, const ll &a) { std::fprintf(stream, "%lld", a); } static inline void print_impl(FILE *stream, const i128 &a) { std::fputs(to_string(a).c_str(), stream); } static inline void print_impl(FILE *stream, const unsigned char &a) { std::fprintf(stream, "%hhu", a); } static inline void print_impl(FILE *stream, const unsigned short &a) { std::fprintf(stream, "%hu", a); } static inline void print_impl(FILE *stream, const unsigned int &a) { std::fprintf(stream, "%u", a); } static inline void print_impl(FILE *stream, const unsigned long &a) { std::fprintf(stream, "%lu", a); } static inline void print_impl(FILE *stream, const ull &a) { std::fprintf(stream, "%llu", a); } static inline void print_impl(FILE *stream, const u128 &a) { std::fputs(to_string(a).c_str(), stream); } static inline void print_impl(FILE *stream, const float &a) { std::fprintf(stream, "%.15f", a); } static inline void print_impl(FILE *stream, const double &a) { std::fprintf(stream, "%.15lf", a); } static inline void print_impl(FILE *stream, const ld &a) { std::fprintf(stream, "%.15Lf", a); } static inline void print_impl(FILE *stream, const std::type_info &a) { std::fputs(a.name(), stream); } template static inline void print_impl(FILE *stream, const std::pair &a) { print_impl(stream, a.first); putc_unlocked(' ', stream); print_impl(stream, a.second); } #if __has_include() || defined(MOD_EXPAND) static inline void print_impl(FILE *stream, const mint &a) { std::fprintf(stream, "%u", a.val()); } #endif template, std::nullptr_t> = nullptr> static inline void print_impl(FILE *stream, const T &a) { if constexpr(std::tuple_size_v != 0) { print_impl_tuple_impl( stream, a, std::make_index_sequence - 1>()); } } template, std::nullptr_t> = nullptr> static inline void print_impl(FILE *stream, const T &a) { if(a.begin() == a.end()) return; print_impl(stream, *(a.begin())); if constexpr(!has_value_type || !has_iterator) { std::for_each(std::next(a.begin()), a.end(), [stream](const auto &value) { putc_unlocked(' ', stream); print_impl(stream, value); }); } else if constexpr( !has_value_type || !has_iterator) { std::for_each(std::next(a.begin()), a.end(), [stream](const auto &value) { putc_unlocked('\n', stream); print_impl(stream, value); }); } else { std::for_each(std::next(a.begin()), a.end(), [stream](const auto &value) { putc_unlocked('\n', stream); putc_unlocked('\n', stream); print_impl(stream, value); }); } } template, std::nullptr_t> = nullptr> static inline void print_impl(FILE *stream, const T &a) { a.print_impl(stream); } static inline void print_impl(...) { print_impl(stderr, "not supported"); } private: template static inline void print_impl_tuple_impl(FILE *stream, const T &A, std::index_sequence) { print_impl(stream, std::get<0>(A)); using swallow= std::initializer_list; swallow{ (putc_unlocked(' ', stream), print_impl(stream, std::get(A)), 0)...}; } }; inline void print() { putc_unlocked('\n', stdout); } template inline void print(Head &&H, Tail &&...T) { out::print_impl(stdout, std::forward(H)); using swallow= std::initializer_list; swallow{ (putc_unlocked(' ', stdout), out::print_impl(stdout, std::forward(T)), 0)...}; putc_unlocked('\n', stdout); } template inline void print_flush(Args &&...args) { print(std::forward(args)...); std::fflush(stdout); } template inline void debug([[maybe_unused]] Args &&...args) { #ifdef _DEBUG print_flush(std::forward(args)...); #endif } inline void print_err() { putc_unlocked('\n', stderr); } template inline void print_err(Head &&H, Tail &&...T) { out::print_impl(stderr, std::forward(H)); using swallow= std::initializer_list; swallow{ (putc_unlocked(' ', stderr), out::print_impl(stderr, std::forward(T)), 0)...}; putc_unlocked('\n', stderr); } [[noreturn]] inline void flush_exit() { std::fflush(stdout); std::_Exit(0); } #pragma endregion /* modpow */ /* O(logN) */ /* define 0^0 as 1 */ /* constraint : 0 <= a */ /* 0 <= b */ /* 0 <= m */ constexpr ll modpow(ull a, ull b, ull m= mod) { ull res= 1ull; if(m < (1ull << 32)) { for(a%= m; b; a= a * a % m, b>>= 1) { if(b & 1ull) res= res * a % m; } return res % m; } else { for(; b; a= static_cast(static_cast(a) * a % m), b>>= 1) { if(b & 1ull) res= static_cast(static_cast(res) * a % m); } return res % m; } } /* pow */ /* O(logN) */ ll bipow(ll a, ll b) { ll res= 1; for(; b; a= a * a, b>>= 1) { if(b & 1) res= res * a; } return res; } signed main() { setvbuf(stdin, nullptr, _IOFBF, 1 << 17); setvbuf(stdout, nullptr, _IOFBF, 1 << 17); LL(M, D, N, B); if(M == 0) { M= 1; N--; if(N == 0) { print(1); return 0; } } ll phi= 0; ll phiphi= 1; ll phiphiphi= 1; if(B == 2 || B == 3 || B == 5 || B == 7 || B == 11) { phi= B - 1; } else if(B == 4 || B == 6) { phi= 2; } else if(B == 9) { phi= 6; } else { phi= 4; } if(phi == 2 || phi == 1) { phiphi= 1; } else if(phi == 4 || phi == 6) { phiphi= 2; } else if(phi == 10) { phiphi= 4; } if(phiphi == 2 || phiphi == 1) { phiphiphi= 1; } else if(phi == 4) { phiphiphi= 2; } vector table(B, vector(phi, vector(phiphi, vec>(phiphiphi)))); vector walk(B, vector(phi, vector(phiphi, vec(phiphiphi, -1)))); debug(B, phi, phiphi, phiphiphi); REP(i, B) { REP(j, phi) { REP(k, phiphi) { REP(l, phiphiphi) { table[i][j][k][l]= { modpow(i + D, j + phi, B), modpow(j + D, k + phiphi, phi), modpow(k + D, l + phiphiphi, phiphi), (l + D) % phiphiphi}; } } } } array now= {M % B, M % phi, M % phiphi, M % phiphiphi}; if(M <= 10) { now= { modpow(now[0] + D, M, B), modpow(now[1] + D, M, phi), modpow(now[2] + D, M, phiphi), (now[3] + D) % phiphiphi}; N--; } ll count= 0; while(walk[now[0]][now[1]][now[2]][now[3]] == -1) { debug(now); walk[now[0]][now[1]][now[2]][now[3]]= count; if(count != 0) N--; count++; if(N == 0) { if(now[0] == 10) { print("A"); } else { print(now[0]); } return 0; } now= table[now[0]][now[1]][now[2]][now[3]]; } ll size= count - walk[now[0]][now[1]][now[2]][now[3]]; N%= size; if(N == 0) { if(now[0] == 10) { print("A"); } else { print(now[0]); } return 0; } while(1) { N--; if(N == 0) { if(now[0] == 10) { print("A"); } else { print(now[0]); } return 0; } now= table[now[0]][now[1]][now[2]][now[3]]; } }