Sesja

Jasio chciałby zobaczyć chociaż sześć ostatnich cyfr bardzo dużej liczby 123456^{100000000000000000000}. (1 i dwadzieścia zer) Czy możesz mu w tym pomóc?

Wejście:

Program nic nie pobiera na wejściu.

Wyjście:

Sześć ostatnich cyfr liczby 123456^{10^20}, zakończona znakiem nowej linii.

---

Wskazówka:
Skorzystaj ze wzoru
(a * b mod c) = ((a mod c) * (b mod c)) mod c
oraz szybkiego potęgowania.