#include #include namespace nachia{ template struct StaticModint{ private: using u64 = unsigned long long; unsigned int x; public: using my_type = StaticModint; StaticModint() : x(0){} StaticModint(unsigned int v) : x(v){} unsigned int operator*() const { return x; } my_type& operator+=(const my_type& r){ auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator+(const my_type& r) const { my_type res = *this; return res += r; } my_type& operator-=(const my_type& r){ auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; } my_type operator-() const { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; } my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; } my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; } my_type pow(unsigned long long i) const { my_type a = *this, res = 1; while(i){ if(i & 1) res *= a; a *= a; i >>= 1; } return res; } my_type inv() const { return pow(MOD-2); } unsigned int val() const { return x; } static unsigned int get_mod() { return MOD; } my_type& operator/=(const my_type& r){ return operator*=(r.inv()); } my_type operator/(const my_type& r) const { return operator*(r.inv()); } }; } namespace nachia{ template struct PrimitiveRoot{ static constexpr unsigned long long powm(unsigned long long a, unsigned long long i) { unsigned long long res = 1, aa = a; while(i){ if(i & 1) res = res * aa % MOD; aa = aa * aa % MOD; i /= 2; } return res; } static constexpr bool examine_val(unsigned int g){ unsigned int t = MOD - 1; for(unsigned long long d=2; d*d<=t; d++) if(t % d == 0){ if(powm(g, (MOD - 1) / d) == 1) return false; while(t % d == 0) t /= d; } if(t != 1) if(powm(g, (MOD - 1) / t) == 1) return false; return true; } static constexpr unsigned int get_val(){ for(unsigned int x=2; x #include using namespace std; using i64 = long long; using u64 = unsigned long long; using i32 = int; using u32 = unsigned int; #define rep(i,n) for(int i=0; i<(n); i++) using m32 = nachia::StaticModint<90007>; i64 rev_int(i64 x){ string a = to_string(x); reverse(a.begin(), a.end()); i64 ans = 0; for(auto c : a) ans = ans * 10 + (c - '0'); return ans; } int main() { i64 P,Q,x,y; cin >> P >> Q >> x >> y; i64 rev_off = y; while(rev_off % 10 == 0 || rev_int(rev_off) % 90007 == 0) rev_off += y; i64 rev_aoff = Q; while(rev_int(rev_aoff) % 90007 == (90007 - rev_int(rev_off) % 90007) % 90007) rev_aoff += Q; string rev_stry = to_string(rev_off); reverse(rev_stry.begin(), rev_stry.end()); string rev_strQ = to_string(rev_aoff); reverse(rev_strQ.begin(), rev_strQ.end()); i64 rev_y = 0; for(auto a : rev_stry) rev_y = rev_y * 10 + a - '0'; i64 rev_Q = 0; for(auto a : rev_strQ) rev_Q = rev_Q * 10 + a - '0'; m32 r_ans = m32(10).pow(rev_strQ.size()) * rev_y; m32 off_ans = m32(rev_Q); int len_r_ans = 0; while((r_ans + off_ans).val() != x){ len_r_ans++; r_ans *= 10; } cout << rev_stry << string(len_r_ans, '0') << rev_strQ << "\n"; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;