DIGITROOT  Digit Root
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 th Eth power).
Input
The input consists of two lines. The first contains the number B (1 ≤ B ≤ 10^{105}). The second contains the number E (1 ≤ E ≤ 10^{105}).
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:
20190305 20:15:32
good question for mathmatics 

julkas:
20181230 13:20:10
+5. Last edit: 20190101 12:28:39 

navin_chandra:
20181229 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.


Francisco Elio Parente Arcos Filho [UEA]:
20181228 19:18:13
Look your code carrefully... its something wrong. Maybe you should look at the limits too. Last edit: 20181228 19:22:06 

mehmetin:
20181228 18:42:02
I was accepted with Python 2.7, now I get wrong answer with c++14...?? Last edit: 20181230 09:41:31 
Added by:  Francisco Elio Parente Arcos Filho [UEA] 
Date:  20181226 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  C C++ 4.3.2 CPP CPP14 CPP14CLANG C99 JAVA 