import java.math.BigInteger;

class RSA {
    
    public static void main(String[] args) {
        BigInteger n = new BigInteger("4111577933");
        BigInteger p = new BigInteger("62731");
        BigInteger q = new BigInteger("65543");
        BigInteger e = new BigInteger("63139");
        BigInteger z = p.add(new BigInteger("-1"))
                    .multiply(q.add(new BigInteger("-1")));
        
        BigInteger[] asd = euclid(e, z);
        
        System.out.println(asd[0].add(n)+ " * " + e + " + " +  asd[1] + " * " + z + " = " + asd[2]);
        BigInteger c = new BigInteger("1210034980");
        
        BigInteger m = c.modPow(asd[0].add(n), n);
        System.out.println(m);
    }
    public static BigInteger[] euclid(BigInteger a, BigInteger b) {
        BigInteger x = new BigInteger("0");
        BigInteger y = new BigInteger("1");
        BigInteger u = new BigInteger("1");
        BigInteger v = new BigInteger("0");
        BigInteger m,n,q,r;
        BigInteger gcd = b;
        
        while (!a.equals(new BigInteger("0"))) {
            q = gcd.divide(a);
            r = gcd.mod(a);
            m = x.subtract(u.multiply(q));
            n = y.subtract(v.multiply(q));
            gcd = a;
            a = r;
            x = u;
            y = v;
            u = m;
            v = n;
        }
        BigInteger[] temp = {x, y, gcd};
        return temp;
    }
}