#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()); } }; } #include #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>; int main() { i64 P,Q,x,y; cin >> P >> Q >> x >> y; string rev_stry = to_string(y); reverse(rev_stry.begin(), rev_stry.end()); string rev_strQ = to_string(Q); 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;