#include <iostream>
#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

#define ll long long

ll val,MOD;

int get_phi(int value){

  int result=1;

  for(int i=2;i*i<=value;++i)
    if (value%i==0){
      int p=1;
      for (;value%i==0&&value>0;)
        p*=i,value/=i;

      result*=(p-p/i);
    }
  if (value>1) result*=(value-1);
  return result;
}

ll lgpow(int P){
    if (P==0) return 1;
    if (P==1) return val;
    if (P%2) return (val*lgpow(P-1))%MOD;
    if (P%2==0) return (lgpow(P/2)*lgpow(P/2))%MOD;
}

int main()
{

  f>>val>>MOD;
  ll phi=get_phi(MOD);
  cout<<phi<<'\n';

  ll result=lgpow(phi-1);

  g<<result;

    f.close();
    g.close();
    return 0;
}