#include <bits/stdc++.h>
using namespace std;
long long powmod(long long base, long long power, long long mod) {
/*
a^b
1. b = genap -> b = 2*k
a^b = a^(2*k) = (a^2)^k
2. b = ganjil -> b = 2*k+1
a^b = a^(2*k+1) = (a^2)^k * a
(a, b) -> (a^2, b/2)
*/
long long hasil = 1;
// hasil*(base^power) == hasil2*((base*base)^(power/2))
while(power > 1) {
if(power%2 == 1)
hasil = (hasil*base)%mod;
base = (base*base)%mod;
power = power/2;
}
hasil = (hasil*base)%mod;
return hasil;
}
int pangkat(int base, int power) { // O(power)
int hasil = 1;
for(int i = 0; i < power; i++)
hasil *= base;
return hasil;
}
int main() {
cout << setfill('0') << setw(6);
cout << powmod(10, 10, 1000000) << endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpsb25nIGxvbmcgcG93bW9kKGxvbmcgbG9uZyBiYXNlLCBsb25nIGxvbmcgcG93ZXIsIGxvbmcgbG9uZyBtb2QpIHsKCS8qCglhXmIKCTEuIGIgPSBnZW5hcCAtPiBiID0gMiprCgkgICBhXmIgPSBhXigyKmspID0gKGFeMileawoJMi4gYiA9IGdhbmppbCAtPiBiID0gMiprKzEKCSAgIGFeYiA9IGFeKDIqaysxKSA9IChhXjIpXmsgKiBhCgkoYSwgYikgLT4gKGFeMiwgYi8yKQoJKi8KCWxvbmcgbG9uZyBoYXNpbCA9IDE7CgkvLyBoYXNpbCooYmFzZV5wb3dlcikgPT0gaGFzaWwyKigoYmFzZSpiYXNlKV4ocG93ZXIvMikpCgl3aGlsZShwb3dlciA+IDEpIHsKCQlpZihwb3dlciUyID09IDEpCgkJCWhhc2lsID0gKGhhc2lsKmJhc2UpJW1vZDsKCQliYXNlID0gKGJhc2UqYmFzZSklbW9kOwoJCXBvd2VyID0gcG93ZXIvMjsKCX0KCWhhc2lsID0gKGhhc2lsKmJhc2UpJW1vZDsKCXJldHVybiBoYXNpbDsKfQoKaW50IHBhbmdrYXQoaW50IGJhc2UsIGludCBwb3dlcikgewkJLy8gTyhwb3dlcikKCWludCBoYXNpbCA9IDE7Cglmb3IoaW50IGkgPSAwOyBpIDwgcG93ZXI7IGkrKykKCQloYXNpbCAqPSBiYXNlOwoJcmV0dXJuIGhhc2lsOwp9CgppbnQgbWFpbigpIHsKCWNvdXQgPDwgc2V0ZmlsbCgnMCcpIDw8IHNldHcoNik7Cgljb3V0IDw8IHBvd21vZCgxMCwgMTAsIDEwMDAwMDApIDw8IGVuZGw7CglyZXR1cm4gMDsKfQ==