Sum of digits of a number raised to a power

Java Medium math

Task «Sum of digits of a number raised to a power»

Given a natural number N and a non-negative integer K. Raise N to the power K and find the sum of the digits of the resulting number. If K is 0, the result is considered to be 1. Output the sum of the digits of the result. It is guaranteed that the result fits into a 64-bit integer.

Input Format

In one line, separated by a space, two integers: N (1 ≤ N ≤ 10^9) and K (0 ≤ K ≤ 10).

Output Format

One integer — the sum of the digits of the number N^K.

Examples

Example 1

INPUT

123 2

OUTPUT

18

main.java