問題文

正整数 $n$ に対し、 $n$ の十進表記(先頭に $0$ を付けない)を左右に反転させて得られる整数を $\mathrm{rev}(n)$ とします。例えば $\mathrm{rev}(1234) = 4321$、$\mathrm{rev}(5000) = 5$ です。

素数 $P,Q$ 及び正整数 $x,y$ が与えられます。ここで $P = 90007$ です。以下の二つの条件を共に満たす $10^{100000}$ 以下の正整数 $N$ を一つ報告してください。

• $N\bmod P=x$
• $\mathrm{rev}(N)\bmod Q=y$

なお、本問題の制約の範囲内では条件を満たす $N$ が必ず存在することが証明できます。

制約

• 入力は全て整数である。
• $P = 90007$
• $2\le Q < 10^{12}$
• $1\le x < P$
• $1\le y < Q$
• $P,Q$ は素数である。

$P$ $Q$ $x$ $y$ 

90007 73 1 1

90008