/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");

/*long long exp_log(short x, long long n, int mod) {
	if(n < 0) {
		x = 1.0 / x;
		n = (-1) * n;
	}
	if(n == 0) return 1;
	long long p = 1;
	x = x % mod;
	while(n > 0) {
		if(n % 2 == 1) {
			p = (p * x) % mod;
		}
		x = (x * x) % mod;
		n /= 2;
	}
	return p;
}*/

long long exp_log(short x, long long n, int mod,int expo) {
	if(n < 0) {
		x = 1.0 / x;
		n = (-1) * n;
	}
	if(n == 0) return 1;
	long long p = 1;
	x = x % mod;
	while(expo > 1) {
		if((n >> (expo-1)) % 2 == 1) {
			p = (p * x) % mod;
		}
		p = (p * p) % mod;
		//n /= 10;
		expo--;
	}
	return p;
}

int binar(long long n, int &expo){
    int rez=0;
    expo = 1;
    while(n){
        rez = rez + expo * (n%2);
        expo*=10;
        n/=2;
    }
    expo/=10;
    int p = expo;
    expo = 0;
    while(p){
        expo +=1;
        p/=10;
    }
    return rez;
}


int main()
{
    short n;
	long long p;
	fin>>n>>p;
	int mod = 1999999973,expo = 1;
	int q = binar(p,expo);
	printf("%d %d\n",q, expo);
	long long s = exp_log(n, q, mod,expo);
	fout<<s;

	return 0;
}