Dividing

Time limit1sMemory limit128 MB

Summary

For each case with t, a, b, decide whether (t^a-1)/(t^b-1) is an integer below 100 digits, and print it or a fixed message.

Level: Medium6 of 10
Topics: Number theory, Math, Implementation, String matching
Solved: No attempts yet

Problem

You are given positive integers $t$ , $a$ , and $b$ , each at most $2147483647$ . For each query, determine whether $\dfrac{t^{a}-1}{t^{b}-1}$ is an integer that has fewer than $100$ digits. If it is such an integer, output its value; otherwise output the fixed message described below.

Input

The input consists of several test cases. Each test case is a single line containing three integers $t$ , $a$ , and $b$ separated by spaces. Input continues until end of file (EOF).

Output

Print one line per test case. First print the expression string (t^a-1)/(t^b-1) with $t$ , $a$ , and $b$ replaced by the given values, then a single space, then the result. If $\dfrac{t^{a}-1}{t^{b}-1}$ is an integer with fewer than $100$ digits, print its value; otherwise print is not an integer with less than 100 digits.

Examples3

Example 1

Input

Expected output

(2^9-1)/(2^3-1) 73
(2^3-1)/(2^2-1) is not an integer with less than 100 digits.
(21^42-1)/(21^7-1) 18952884496956715554550978627384117011154680106
(123^911-1)/(123^1-1) is not an integer with less than 100 digits.

Example 2
Input
```
5 4 4
```
Expected output
```
(5^4-1)/(5^4-1) 1
```
Example 3
Input
```
10 2 1
```
Expected output
```
(10^2-1)/(10^1-1) 11
```