import java.math.BigInteger;
public class Q4{
    public static void main (String[] args) {
        BigInteger e1 = new BigInteger("1106427");
        BigInteger e2 = new BigInteger("422068");
        BigInteger n = new BigInteger("1397197");
        //Run Ex. GCD to solve for X
        BigInteger x = e1.modInverse(e2);
        System.out.println("x is "+x);
        //Use this answer to solve for y.
        BigInteger temp = e1.multiply(x).subtract(new BigInteger("1"));
        BigInteger y = temp.divide(e2);
        System.out.println("y is "+y);

        // The key is this: M^(e1x+e2y) = M mod n
        // Thus, we need to calculate M^e1x mod n and M^e2y mod n
        // and multiply these. Since y is negative, we must invert
        // our answer after using the positive version of y, which is
        // stored in the variable y above.
        // Finally, note that c1 = M^e1, so M^e1x is c1^x and
        //                    c2 = M^e2, so M^e2y is c2^y.
        // Two cipher texts.
        BigInteger cipher1 = new BigInteger("1106427");
        BigInteger cipher2 = new BigInteger("422068");

        // c1^x mod n.
        cipher1 = cipher1.modPow(x, n);
        // c2^y mod n, through two steps.
        cipher2 = cipher2.modPow(y, n);
        cipher2 = cipher2.modInverse(n);

        // The answer is the product.
        BigInteger finalanswer = cipher1.multiply(cipher2);
        finalanswer = finalanswer.mod(n);
        System.out.println("M is "+finalanswer);

    }
}