### Problem Statement

A number is a Perfect Square if it can be expressed as k^2 for some positive integer k. A number is a Perfect Power if it can be expressed as k^n (k to the nth power) for some positive integers k and n, where n and k must both be greater than 1.

Create a class Powerful that contains the method power that takes an int, number, as input and returns the String "<k>^<n>", where <k> to the <n>th power is equal to number. If a number cannot be represented as a Perfect Power, your method should return "NOT A PERFECT POWER".

### Definition

 Class: Powerful Method: power Parameters: int Returns: String Method signature: String power(int number) (be sure your method is public)

### Notes

-If there is more than one way to express a number as a Perfect Power, your method should express it with the highest exponent possible. (see example 1)
-Your method should return "<k>^<n>"; (quotes and angle brackets for clarity only) with no blanks or leading zeroes.

### Constraints

-number is between 1 and 2,000,000,000 inclusive.

### Examples

0)

 `8`
`Returns: "2^3"`
1)

 `81`
`Returns: "3^4"`
 Do NOT return "9^2"
2)

 `675`
`Returns: "NOT A PERFECT POWER"`
3)

 `1`
`Returns: "NOT A PERFECT POWER"`
4)

 `2000000000`
`Returns: "NOT A PERFECT POWER"`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=739

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4165&pm=739

dgoodman