/*
* 755@「C/C++の宿題なら俺にやらせろ！」の解答例。
*/
#include <stdio.h>

unsigned long
powmod(unsigned long x, unsigned long y, unsigned long z)
{
　　unsigned long r;
　　for (r = 1; y; y >>= 1) {
　　　　if (y & 1) r = r * x % z;
　　　　x = x * x % z;
　　}
　　return r;
}

int main()
{
　　printf("%lu\n", powmod(12345, 6789012, 34567));
　　return 0;
}