#include <iostream>
#include <cmath>
using namespace std;
 
long long pot_szybkie(long long a, unsigned int n)
{
  if(n==0)
    return 1;
 
  if(n%2 == 1) //gdy n jest nieparzyste
    return a * pot_szybkie(a, n - 1);
 
  //żeby dwa razy nie wchodzić w tą samą rekurencję
  long long w = pot_szybkie(a, n/2); 
  return w * w;
}
 
int main() {
	cout << (int)abs(pot_szybkie(3, 100)) % 10000 << endl;
	cout << (int)pow(3, 100) % 10000;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y21hdGg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKbG9uZyBsb25nIHBvdF9zenlia2llKGxvbmcgbG9uZyBhLCB1bnNpZ25lZCBpbnQgbikKewogIGlmKG49PTApCiAgICByZXR1cm4gMTsKIAogIGlmKG4lMiA9PSAxKSAvL2dkeSBuIGplc3QgbmllcGFyenlzdGUKICAgIHJldHVybiBhICogcG90X3N6eWJraWUoYSwgbiAtIDEpOwogCiAgLy/FvGVieSBkd2EgcmF6eSBuaWUgd2Nob2R6acSHIHcgdMSFIHNhbcSFIHJla3VyZW5jasSZCiAgbG9uZyBsb25nIHcgPSBwb3Rfc3p5YmtpZShhLCBuLzIpOyAKICByZXR1cm4gdyAqIHc7Cn0KIAppbnQgbWFpbigpIHsKCWNvdXQgPDwgKGludClhYnMocG90X3N6eWJraWUoMywgMTAwKSkgJSAxMDAwMCA8PCBlbmRsOwoJY291dCA8PCAoaW50KXBvdygzLCAxMDApICUgMTAwMDA7CglyZXR1cm4gMDsKfQ==