Problem: A long time ago in some far country lived king Copa. After the recent king's reform, he got so large powers that started to keep the books by himself.

The total income A of his kingdom during 0-th year is known, as well as the total income B during n-th year (these numbers can be negative — it means that there was a loss in the correspondent year). 

King wants to show financial stability. To do this, he needs to find common coefficient X — the coefficient of income growth during one year. This coefficient should satisfy the equation:

A·Xn = B.

Surely, the king is not going to do this job by himself, and demands you to find such number X.

It is necessary to point out that the fractional numbers are not used in kingdom's economy. That's why all input numbers as well as coefficient X must be integers. The number X may be zero or negative.

Input

The input contains three integers A, B, n (|A|, |B| ≤ 1000, 1 ≤ n ≤ 10).

Output

Output the required integer coefficient X, or «No solution», if such a coefficient does not exist or it is fractional. If there are several possible solutions, output any of them.

Examples

Input

2 18 2


Output

3

Input

-1 8 3


Output

-2

Input

0 0 10


Output

5

Input

1 16 5


Output

No solution

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main
{
    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[1024]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
		
		public String next() throws IOException
		{
			return readLine();
		}
    }
	
	static int root(int arr[] , int x)
	{
		while(arr[x] != x)
		{
			arr[x] = arr[arr[x]];
			x  = arr[x];
		}
		return x;
	}
	
	static void union_find(int arr[] , int size[] , int x , int y)
	{
		int root_x = root(arr , x);
		int root_y = root(arr , y);
		
		if(root_x != root_y)
		{
			if(size[root_x] > size[root_y])
			{
				arr[root_y] = arr[root_x];
				size[root_x] += size[root_y];
			}
			else
			{
				arr[root_x] = arr[root_y];
				size[root_y] += size[root_x];
			}
		}
	}
	
	static float fun(float x , int n , int N)
	{
		float f1=0;
		
		f1 = (float)(((n-1)*Math.pow(x,n)+N)/(n*Math.pow(x,n-1)));
		
		return f1;
	}
 
    public static void main(String[] args) throws IOException
    {
        Reader In = new Reader();
		
		int A = In.nextInt();
		int B = In.nextInt();
		int n = In.nextInt();
		
		float arr[] = new float[10000];
		
		arr[0] = 1;
		
		int i = 0 ;
			
		float max = -1000 , min = 1000;
		
		if(n != 0 && A != 0 && B != 0 && (B%A == 0))
		{
			for( ; ; )
			{
				arr[i+1] = fun(arr[i] , n , B/A);
				
				if(arr[i+1] > arr[i])
                {
                    max = arr[i+1];
                    min = arr[i];
                }
                else
                {
                    max = arr[i];
                    min = arr[i+1];
                }
				
                if((max-min) < 0.0001)
                {
					int temp = (int)arr[i+1];
					
					if((arr[i+1] - (int)arr[i+1]) == 0)
						System.out.println((int)arr[i+1]);
					else
						System.out.println("No solution");
					
                    break;
                }                    
				
				i++;
			}
		}
		else if(A != 0 && B == 0)
			System.out.println("0");
		else if(A == 0 && B == 0)
			System.out.println("1");
		else
			System.out.println("No solution");
    }
}