A. Bank
time limit per test
2 seconds
memory limit per test
64 megabytes
input
stdin
output
stdout

You are given an encrypted number, encrypted using a certain algorithm.Decrypt it !

Input

The first line contains keys, n, e (1 ≤ n, e ≤ 106).

Next line contains encrypted number

Output

Print the original number.

Examples
Input
2461 2007
2097
Output
2175
Input
65783 58199
53581
Output
12356
Input
409763 128561
82222
Output
311454