A Digit Root is a feature of numbers used in mathematical recreation, but can also be used to check the results of simple operations such as sum and multiplication. One of its main properties is that the Digit Root of a number is always equal to Digit Root of the sum of its digits.

For example, the Digit Root of 18446744073709551615 is the same as 87 because 1 + 8 + 4 + 4 + 6 + 7 + 4 + 4 + 0 + 7 + 3 + 7 + 0 + 9 + 5 + 5 + 1 + 6 + 1 + 5 = 87, and is the same of 15 because 8 + 7 = 15, which in turn is the same as 6, since 1 + 5 = 6. Therefore the Digit Root of all these numbers is 6 since 6 is its own Digit Root.

Your task is, given the two integers, B and E, calculate the Digit Root of B^E (B raised to the E-th power).

Input

The input consists of two lines. The first contains the number B (1 ≤ B ≤ 10¹⁰⁵). The second contains the number E (1 ≤ E ≤ 10¹⁰⁵).

Output

The output consists of a single line containing theDigit Root.

Example

Input:
2
7
Output:
2

Input:
25
5

Output:
4

Input:
6
10

Output:
9