[NOIP 2013] 转圈游戏

#include<bits/stdc++.h>
using namespace std;

int n,m,k,x;

inline int power(int a,int n,int p)
{
        int b = a,res = 1;
        while (n > 0)
        {
                if (n & 1) res = 1ll * res * b % p;
                b = 1ll * b * b % p;
                n >>= 1; 
        }
        return res;
}

int main() 
{
        
        scanf("%d%d%d%d",&n,&m,&k,&x);
        printf("%d\n",(x + m * power(10,k,n)) % n);
        
        return 0;
    
}