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

public class Primemmx2 {
	static BigInteger zero = new BigInteger("0");
	static BigInteger one = new BigInteger("1");
	static BigInteger two = new BigInteger("2"); 
	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 i = new BigInteger("1");
		BigInteger M = new BigInteger("1");

		for (i=zero; i.compareTo(m)<0; i=i.add(one))
			M = M.multiply(two);
		M = M.subtract(one);

			BigInteger wanless = new BigInteger("0");
			wanless = n.divide(M);
			wanless = wanless.divide(two);

			n=wanless.multiply(M).multiply(two).add(one);

			BigInteger index = new BigInteger("1");
			index = wanless;

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

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

			result = evaluate(m, n);

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();
}

			n=n.add(M.multiply(two));
			index=index.add(one);

} while (result.compareTo(zero)!=0);

			index=index.subtract(one);
			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");
		BigInteger i = new BigInteger("1");
		BigInteger M = new BigInteger("1");

		for (i=zero; i.compareTo(m)<0; i=i.add(one))
			M = M.multiply(two);
		M = M.subtract(one);
		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;
			}
		}
	}

}