import java.math.BigInteger;
import java.util.Random;
import java.util.Date;

public class Primemx2t {
	static BigInteger zero = new BigInteger("0");
	static BigInteger one = new BigInteger("1");
	static BigInteger two = new BigInteger("2"); 
	static BigInteger three = new BigInteger("3"); 
	static BigInteger four = new BigInteger("4"); 
	static BigInteger six = new BigInteger("6");
	static BigInteger THIRTY = new BigInteger("30"); 
	static BigInteger hundredthousand = new BigInteger("100000"); 

	static BigInteger m = new BigInteger("0");
	static BigInteger n = new BigInteger("0");

	static BigInteger t = new BigInteger("0");
	static String s;
	static int s1 = 0;

	public static void main (String args[])
		throws java.io.IOException {

		char c;
		char ch;
		String sInput;
		String sInput2;

		Date d;
		long starttime;
		long finishtime;
		long duration;

		while (true) {
			t = zero;
			s = "";
			s1 = 0;

			StringBuffer sbInput2 = new StringBuffer("");

			while ((c=(char)System.in.read()) != '\n' && c != '\r')
				sbInput2.append(c);
			System.in.read();

			sInput2=sbInput2.toString().trim();

			if (sInput2.charAt(0) == 'f' || sInput2.charAt(0) == 'F') {
				s = sInput2.substring(1).trim();

				eval();

				m = t;

				System.out.println('[' + m.toString() + ']');
			}
			else if (sInput2.charAt(0) == 'r' || sInput2.charAt(0) == 'R') {
				s = sInput2.substring(1).trim();

				BigInteger size = new BigInteger(s);
				Random r = new Random();

				m = new BigInteger(size.intValue(), r);

				System.out.println('[' + m.toString() + ']');
			}
			else {
				m = new BigInteger(sInput2);
			}
			
			

			t = zero;
			s = "";
			s1 = 0;

			StringBuffer sbInput = new StringBuffer("");

			while ((c=(char)System.in.read()) != '\n' && c != '\r')
				sbInput.append(c);
			System.in.read();

			sInput=sbInput.toString().trim();

			if (sInput.charAt(0) == 'f' || sInput.charAt(0) == 'F') {
				s = sInput.substring(1).trim();

				eval();

				n = t;

				System.out.println('[' + n.toString() + ']');
			}
			else if (sInput.charAt(0) == 'r' || sInput.charAt(0) == 'R') {
				s = sInput.substring(1).trim();

				BigInteger size = new BigInteger(s);
				Random r = new Random();

				n = new BigInteger(size.intValue(), r);

				System.out.println('[' + n.toString() + ']');
			}
			else {
				n = new BigInteger(sInput);
			}
			
			
			
			BigInteger result = new BigInteger("0");

			BigInteger M = new BigInteger("1");
			M = m;

			BigInteger twoM = new BigInteger("1");
			twoM = M.multiply(two);
			
			BigInteger fourM = new BigInteger("1");
			fourM = M.multiply(four);
			
			BigInteger sixM = new BigInteger("1");
			sixM = M.multiply(six);
			


			n = n.divide(twoM).divide(THIRTY).multiply(twoM).multiply(THIRTY).add(one);


			BigInteger index = new BigInteger("1");
			index = n.divide(twoM);




			d = new Date();
			starttime = d.getTime();

do {

if (index.remainder(hundredthousand).compareTo(THIRTY)==0) {
			d = new Date();
			starttime = d.getTime();
}

            result = evaluate(m,n); // mod=1
			if (result.compareTo(zero)==0) break;
            n = n.add(sixM); // mod=2,3,4,5,6 skipped
			index = index.add(three);

            result = evaluate(m,n); // mod=7
			if (result.compareTo(zero)==0) break;
            n = n.add(fourM); // mod=8,9,10 skipped
			index = index.add(two);

            result = evaluate(m,n); // mod=11
			if (result.compareTo(zero)==0) break;
            n = n.add(twoM); //mod=12 skipped
			index = index.add(one);

            result = evaluate(m,n); // mod=13
 			if (result.compareTo(zero)==0) break;
            n = n.add(fourM); // mod=14,15,16 skipped
			index = index.add(two);

            result = evaluate(m,n); // mod=17
			if (result.compareTo(zero)==0) break;
            n = n.add(twoM); // mod=18 skipped
			index = index.add(one);

            result = evaluate(m,n); // mod=19
			if (result.compareTo(zero)==0) break;
            n = n.add(fourM); // mod=20,21,22 skipped
			index = index.add(two);

            result = evaluate(m,n); // mod=23
			if (result.compareTo(zero)==0) break;
            n = n.add(sixM); // mod=24,25,26,27,28 skipped
			index = index.add(three);

            result = evaluate(m,n); // mod=29
			if (result.compareTo(zero)==0) break;
            n = n.add(twoM); // mod 30 skipped
			index = index.add(one);


if (index.remainder(hundredthousand).compareTo(zero) == 0) {
			System.out.println("m = " + m.toString() + '\t' + "index = " + index.toString() + '\t' + "n = " + n.toString() + '\t' + "T = " + result.toString());
			
			d = new Date();
			finishtime = d.getTime();

			duration = (finishtime-starttime)/1000;

			System.out.println("duration: " + duration + " seconds");

			System.out.println();
}

} while (true);

			System.out.println("m = " + m.toString() + '\t' + "index = " + index.toString() + '\t' + "T = " + result.toString());


		}
	}


	public static BigInteger evaluate(BigInteger m, BigInteger n) {
		BigInteger T = new BigInteger("1");

		T = two.modPow(m, n).add(one).mod(n);

		return T;
	}
	

	public static BigInteger evalPower(BigInteger oldn, BigInteger n1, char op) {
		BigInteger n = new BigInteger("0");

		switch (op) {
		case '^':
		case '#':
			n = oldn.pow(n1.intValue());
			break;
		default:
			n = n1;
			break;
		}
		return n;
	}

	public static BigInteger evalProduct(BigInteger oldn, BigInteger n1, char op) {
		BigInteger n = new BigInteger("0");

		switch (op) {
		case '*':
			n = oldn.multiply(n1);
			break;
		case '/':
			n = oldn.divide(n1);
			break;
		case '%':
			n = oldn.remainder(n1);
			break;
		default:
			n = n1;
			break;
		}
		return n;
	}

	public static BigInteger evalSum(BigInteger oldn, BigInteger n1, char op) {
		BigInteger n = new BigInteger("0");

		switch (op) {
		case '+':
			n = oldn.add(n1);
			break;
		case '-':
			n = oldn.subtract(n1);
			break;
		default:
			n = n1;
			break;
		}
		return n;
	}

	public static void eval() {
		BigInteger oldn0 = new BigInteger("0");
		BigInteger oldn1 = new BigInteger("0");
		BigInteger oldn2 = new BigInteger("0");
		BigInteger n = new BigInteger("0");

		char oldop0 = 0;
		char oldop1 = 0;
		char oldop2 = 0;
		char op = 0;

		int olds1 = 0;

		while (s1 < s.length()) {
			if (s1 < s.length() && (s.charAt(s1) == '(' || s.charAt(s1) == '[' || s.charAt(s1) == '{')) {
				s1++;
				eval();
				n = t;
			}
			else if (s1 < s.length()) {
				olds1 = s1;
				while (s1 < s.length() && Character.isDigit(s.charAt(s1)))
					s1++;
				n = new BigInteger(s.substring(olds1, s1));
			}

			if (s1 < s.length()) {
				op = s.charAt(s1);
				s1++;
			}
			else
				op = 0;

			switch (op) {
				case 0:
				case ')':
				case ']':
				case '}':
					n = evalPower(oldn2, n, oldop2);
					n = evalProduct(oldn1, n, oldop1);
					n = evalSum(oldn0, n, oldop0);
					t = n;
					return;

				case '^':
				case '#':
					n = evalPower(oldn2, n, oldop2);
					oldn2 = n;
					oldop2 = op;
					break;

				case '*':
				case '/':
				case '%':
					n = evalPower(oldn2, n, oldop2);
					oldop2 = 0;
					n = evalProduct(oldn1, n, oldop1);
					oldn1 = n;
					oldop1 = op;
					break;

				case '+':
				case '-':
					n = evalPower(oldn2, n, oldop2);
					oldop2 = 0;
					n = evalProduct(oldn1, n, oldop1);
					oldop1 = 0;
					n = evalSum(oldn0, n, oldop0);
					oldn0 = n;
					oldop0 = op;
					break;
				default:
					break;
			}
		}
	}

}