//version 1
//version 1.p ported 14:00 55 PST on Jan-9-2004
//Jacques Le Normand
//ported by "landen" and "ludwig"
//special thanks to "Polytope"
//jacqueslen@sympatico.ca
//g++ -O3 egypt.cpp
#include <iostream>
#include <vector>
#include <set>
#if defined __GNUC__
typedef long long INT64;  // must be 64 bit integer on your compiler
typedef long INT32;  // must be 32 big integer on your compiler
#include <cmath>
#endif

#if defined _WIN32
#include <iomanip>
#include <stdio.h>
#include <conio.h>
#include <cmath>
#include <sys/timeb.h>
#include <time.h>
typedef __int64 INT64; // must be 64 bit integer on your compiler
typedef __int32 INT32; // must be 32 bit integer on your compiler
#endif

//always place headers before this line (to avoid corrupting the namespace)
using namespace std;

//if n=8, use big as 97.... if n<=7, use big as 100000.
//note: big dictates how much memory is needed, using big=6526886
//will take up about a gig of memory
const INT32 N=8;
const INT32 big = (N<8)?100000:9790328;
INT32 progress = 0;
pair<INT32,char>** factorlist;
vector<char> factorindex;
vector<char> sieve;

class fastvec{
public:
    pair<INT32,INT32> data[14];
    INT32 size;
    INT32& operator[](INT32 a){
	for(INT32 i = 0 ; i < size ; i++){
	    if(data[i].first==a) return data[i].second;
	}
	data[size].first=a;
	data[size].second=0;
	size++;
	return data[size-1].second;
    }
    void erase(INT32 a){	
	for(INT32 i = 0 ;i < size ; i++){
	    if(data[i].first==a){		
		data[i]=data[size-1];
		size--;
		return;
	    }
	}
    }
    fastvec(){
	size = 0;
    }
};
fastvec sofar;
fastvec tempfar;
void checkprimefact(INT64 a){
    INT64 s = 1;
    for(INT32 i = 0 ; i < tempfar.size; i++)
	for(INT32 j = 0; j < tempfar.data[i].second; j++)
	    s*=tempfar.data[i].first;
    if(s!=a) {
			
#if defined __GNUC__
	cout << a << " = " << endl;	
#endif
			
#if defined _WIN32
	char buffer[20];
	cout << _i64toa(a,buffer,10) << " = " << endl;	
#endif
			
	for(INT32 i = 0 ; i < tempfar.size; i++)
	    cout << tempfar.data[i].first << "^" << tempfar.data[i].second << " * ";
	exit(0);
    }
}


void checkprimefact2(INT64 a){
    INT64 s = 1;
    for(INT32 i = 0 ; i < sofar.size; i++)
	for(INT32 j = 0; j < sofar.data[i].second; j++)
	    s*=sofar.data[i].first;
    if(s!=a) {
			
#if defined __GNUC__
	cout << a << " = " << endl;	
#endif
			
#if defined _WIN32
	char buffer[20];
	cout << _i64toa(a,buffer,10) << " = " << endl;	
#endif
	for(INT32 i = 0 ; i < sofar.size; i++)
	    cout << sofar.data[i].first << "^" << sofar.data[i].second << " * ";
	exit(0);
    }
}

//returns a value greater than the square root of n
/*
  INT32 ceil_sqrt(INT32 n)
  {
  INT32 k_old, k_new;
  if (n == 0) return 0;
  k_old = n;
  while (1) { // there are rare cases in which it is necessary to do this
  k_new = (n/k_old + k_old)/2;
  if (k_new >= k_old) return k_old+1; // k_new > k_old is round-off error
  k_old = (n/k_new + k_new)/2;
  if (k_old >= k_new) return k_new+1;
  } 
  }
*/

INT32 ceil_sqrt(INT32 n) // returns 1 more than the floor
{
    return ((INT32) floor(sqrt((double) n)) + 1);
}

//sets the sieve, to check primality. n is prime iff sieve[n]==0
void set_primes(){    
    sieve = vector<char>(big);
    for(INT32 i = 2 ; i < big; i ++){
	if(sieve[i]) continue;
	for(INT32 j = i*2; j < sieve.size() ; j+=i){
	    sieve[j]=1;
	}
    }
}    

//primality testing
bool isprime( INT32 n){
    return (sieve[n]==0);
}

//returns a factor of n
INT64 factor( INT32 n){
    if(isprime(n)) return 1;
    INT32 to_check = ceil_sqrt(n)+10; //sqrt((INT32 double) n) + 10;
    for(INT32 i = 2 ; i < to_check ; i++){
	if(n%i == 0 && isprime(i)) return i;
    }
    return -1;
}
//factorlist[n] returns a vector of primes, and their multiplicity. for example, factorlist[12]=[[2,2],[3,1]]
void set_factors(){
    INT32 i,j;
    //    factorlist = vector<vector<pair<INT32,char> > >(big,vector<pair<INT32,char> >(8));
    factorlist = new pair<INT32,char>*[big];
    /*    for(i= 0 ; i < big ; i++){
	  factorlist[i]=new pair<INT32,char>[9];
	  }*/
    factorindex = vector<char>(big);
    fill(factorindex.begin(),factorindex.end(),-1);
    for(i = 2 ; i < big ; i++){
	j = i;
	set<INT32> seen;
	while(!isprime(j)){
	    INT32 d= factor(j);
			
	    if(d!=1) seen.insert(d);
	    j/=d;
			
	}
	if(j!=1) seen.insert(j);
	factorlist[i]=new pair<INT32,char>[seen.size()];
	factorlist[i][0].first=-1;
	j=i;
		
	while(!isprime(j)){
	    INT32 d= factor(j);
	    if(factorindex[i]==-1 || d!=factorlist[i][factorindex[i]].first) {
		factorindex[i]++;
		if(factorindex[i]>=seen.size()) cout << "ERROR" << endl;
		factorlist[i][factorindex[i]].first=d;
	    }
	    factorlist[i][factorindex[i]].second++;
	    j/=d;
	}
	if(j!=factorlist[i][factorindex[i]].first) {
	    factorindex[i]++;
	    if(factorindex[i]>=seen.size()) cout << "ERROR" << endl;
	    factorlist[i][factorindex[i]].first=j;
	}
	factorlist[i][factorindex[i]].second++;
		
    }
}
//this is the meat. it generates all the divisors of denum, and then tests using Polytope's test. sofar contains all the prime divisors of denum and their multiplicity. sofar is like a map.

INT32 get_divisors( INT32& num,INT64& denum,INT64 d,INT32 c,INT32 start){
	
    INT32 i, ret=0;
    if(c>=tempfar.size){
	//	if((denum+d)%num==0 && ((((denum%num)*(denum%num)) + (d%num)*(denum%num))%num==0))
	if((denum+d)%num==0)
	    if((denum+d)/num>=start) return 1;	
	return 0;
    }
    //    checkprimefact(denum);
    while((num%tempfar.data[c].first)==0 && tempfar.data[c].second>0){
	num/=tempfar.data[c].first;
	denum/=tempfar.data[c].first;
	tempfar.data[c].second--;
		
    }    
    //    checkprimefact(denum);
    for(i = 0; i <= tempfar.data[c].second*2; i++){
	ret+=get_divisors(num,denum,d,c+1,start);
	d*=tempfar.data[c].first;
	if(d>denum) break;
    }
    return ret;
}

//standard brute force, with a special case when n = 2.    
INT64 func(INT32 n, INT32 num,INT64 denum, INT32 start){
    if(n==2){	
	for(INT32 i= 0 ; i < sofar.size; i++){
	    tempfar.data[i]=sofar.data[i];
	    tempfar.size=sofar.size;
	}
	progress++;
	if(progress%1000000 ==0) cout << (progress/1520000) << endl;
	return get_divisors(num,denum,1,0,start);
    }
    INT32 i;
    INT64 least,ret,bot;
    INT32 to_check,top;
    to_check = (denum * n) / num;
    if(denum%num)
	least = ((denum+num-1 )/num);
    else
	least = (denum/num)+1;
    if(start < least)
	start = least;
    ret = 0;
    for(; to_check >= start; to_check--){
		
	top = num * to_check - denum;
	bot = to_check * denum;
	for(i = 0; i <= factorindex[to_check]; i++){
	    sofar[factorlist[to_check][i].first]+=factorlist[to_check][i].second;	    
	}
	ret+=func(n-1,top,bot,to_check);
	if((ret >> 32) >0 ) {cout << "OVERFLOW" << endl; exit(0);}
	for(i = 0; i <= factorindex[to_check]; i++){
	    sofar[factorlist[to_check][i].first]-=factorlist[to_check][i].second;
	    if(sofar[factorlist[to_check][i].first]<=0) sofar.erase(factorlist[to_check][i].first);
	}	
    }
    return ret;
}


int main(){	  // must be int and not long or anything else.
    cout << "memory usage will be about " << ((big * 40L)>>20) << " megs. Here we go!" << endl;	    
    set_primes();
    set_factors();
    //func(n,1,1,2) will calculate it for n terms, n <=8 
#if defined __GNUC__
    //	factorlist = new vector<pair<INT32,char> >[big];
    cout << func(N,1,1,2) << endl;
    cout << "finished" << endl;
#endif
	
#if defined _WIN32
    double duration;
    char buffer[20];
    INT64 total;
    clock_t t1,t2;
    t1 = clock();
    total = func(N,1,1,2); 
    t2 = clock();
	
    duration = (double)(t2 - t1) / CLOCKS_PER_SEC;
    printf( "%4.3f seconds\n", duration );
    cout << "total number of fractions: " << _i64toa(total,buffer,10);

    char foo;
    cin >> foo;
#endif
    return 0;
}