Hide

Problem D
Basic Remains

/problems/basicremains/file/statement/en/img-0001.jpg

Given a base $b$ and two non-negative base-$b$ integers $p$ and $m$, compute $p \bmod m$ and print the result as a base $b$ integer. $p \bmod m$ is defined as the smallest non-negative integer $k$ such that $p = am + k$ for some integer $a$.

Input

Input consists of a number of cases (at most $1000$). Each case is represented by a line containing three non-negative integers. The first, $b$, is a base-$10$ number between $2$ and $10$. The second, $p$, contains up to $1000$ digits between $0$ and $b-1$. The third, $m$, contains up to $9$ digits between $0$ and $b-1$. The last case is followed by a line containing $0$.

Output

For each test case, print a line giving $p \bmod m$ as a base-$b$ integer.

Sample Input 1 Sample Output 1
2 1100 101
10 123456789123456789123456789 1000
0
10
789

Please log in to submit a solution to this problem

Log in