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


Input

Input consists of a number of cases. Each case is represented by a line containing three unsigned integers. The first, b, is a decimal 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 mod m as a base-b integer. 


Sample Input

2 1100 101
10 123456789123456789123456789 1000
0


Sample Output

10
789

我的程序是：
//***** Big Number division *********************//
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define MAX 1002
using namespace std;
/*******************************************************************/
int call_div(char *number, long div, char *result, int ary)
{
        int len=strlen(number);
        int now;
        long extra;
        char Res[MAX];
        for(now=0,extra=0;now<len;now++)
  {
                extra=extra*ary + (number[now]-'0');    //changed!
                Res[now]=extra / div +'0';
                extra%=div;
        }
        Res[now]='\0';
        for(now=0;Res[now]=='0';now++);
        strcpy(result, &Res[now]);
        if(strlen(result)==0)
                strcpy(result, "0");
        return extra;
}
/*************!!!!!!!!!!!!****************/
long ary_change(char *src, int n)
{
    long num_ary_ten = 0;
    int len_src=strlen(src), i=0;
    for(i=0; i<len_src; i++)
    {
        num_ary_ten = num_ary_ten*n + (src[i]-'0');              
    }

    return num_ary_ten;
}

int ary_rechange(long num, int ary, int *res)
{
    int i=0;
    int tmp[100];
    int index=0;
    while(num)
    {
         tmp[index++] = num%ary;
         num /= ary;     
    }
    for(i=index-1; i>=0; i--)
    {
        res[index-1-i] = tmp[i];       
    }
    
    return index;
}

int main()
{
    int ary=0, Remain_len=0;
    char fir[MAX],res[MAX],sec_str[10];
    int Remainder[MAX];
    long sec=0, remainder=0;
    while(cin >> ary)
    {
        if(ary==0)
        {         
            break;          
        }
        cin >> fir >> sec_str;
        sec = ary_change(sec_str, ary);
        remainder=call_div(fir, sec, res, ary);
        Remain_len = ary_rechange(remainder, ary, Remainder);
        for(int i=0; i<Remain_len; i++)
        {
            cout << Remainder[i]; //余数
        }
        cout << endl;
    }
    return 0;
}
题目所给测试数据都没有问题，自己又试了几组，也没有问题。。。。。
可是AC不了