DIGITROOT - Digit Root

no tags 

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 BE (B raised to th E-th power).

Input

The input consists of two lines. The first contains the number B (1 ≤ B ≤ 10105). The second contains the number E (1 ≤ E ≤ 10105).

Output

The output consists of a single line containing theDigit Root.

Example

Input:

2

7

Output: 2

Example

Input:

25

5

Output: 4

Example

Input:

6

10

Output: 9

hide comments
pandey101299: 2019-03-05 20:15:32

good question for mathmatics

julkas: 2018-12-30 13:20:10

+5.

Last edit: 2019-01-01 12:28:39
navin_chandra: 2018-12-29 20:12:04

Apply Mathematics otherwise it is not accepted because range are very very large.It can not be calculated in given time interval.
AC in c language :)

Last edit: 2018-12-29 20:22:29
Francisco Elio Parente Arcos Filho [UEA]: 2018-12-28 19:18:13

Look your code carrefully... its something wrong. Maybe you should look at the limits too.

Last edit: 2018-12-28 19:22:06
mehmetin: 2018-12-28 18:42:02

I was accepted with Python 2.7, now I get wrong answer with c++14...??

Last edit: 2018-12-30 09:41:31

Added by:Francisco Elio Parente Arcos Filho [UEA]
Date:2018-12-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA