C++ :

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lf else if

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

int a,n,res;

int cal(int p,int c,int q){
	if (p==2&&q==2) return 2;
	int res=1,phi;
	For(i,0,c){
		phi=q/p*(p-1);
		if (i%a==0){
			if (p==2&&a%2==0&&phi>1){
				res+=phi/2/__gcd(phi/2,a);
			} else{
				res+=phi/__gcd(phi,a);
			}
		}
		q/=p;
	}
	return res;
}

int main(){
	scanf("%d%*d%d",&a,&n);
	res=1;
	for (int i=2;1ll*i*i<=n;i++)
		if (n%i==0){
			int p=i,q=1,c=0;
			while (n%i==0) n/=i,c++,q*=i;
			res*=cal(p,c,q);
		}
	if (n>1) res*=cal(n,1,n);
	printf("%d\n",res);
}