Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8824

Jo'natishlar soni: 714622

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1177


So'ngi izohlar

739. Sequence
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

  In a sequence of numbers a1, a2, a3, ... given the first term, and the rest are calculated using the formula:

ai = (ai-1)2 mod 10000.

   Find the N-th term of the sequence.

Input

In the first row are the numbers a1 and N, separated by a space. 0  a1  10000, 1  N  2000000010.

Output

Output a single number - aN.

Samples

Input

Output

1

4 3

256

2

0 2000

0

 

Tayyorladi: Azat Yusupov
Text from: e-olimp.com
Mening urinishlarim(0) Muhokama (0) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(26) Barcha urinishlar(104)