chyx's Blog

import java.util.*;
import java.math.*;
import java.io.*;

class Fraction{
	BigInteger den, num;
	Fraction(){}
	Fraction(int a){
		den = BigInteger.ONE;
		num = BigInteger.valueOf(a);
	}
	Fraction(BigInteger a){
		den = BigInteger.ONE;
		num = a;
	}
	void simplify(){
		BigInteger gcd = den.gcd(num);
		den = den.divide(gcd);
		num = num.divide(gcd);
	}
	Fraction subtract( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.den );
		c.num = num.multiply( b.den ).subtract( b.num.multiply( den ) );
		c.simplify();
		return c;
	}
	Fraction add( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.den );
		c.num = num.multiply( b.den ).add( b.num.multiply( den ) );
		c.simplify();
		return c;
	}
	Fraction multiply( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.den );
		c.num = num.multiply( b.num );
		c.simplify();
		return c;
	}
	Fraction divide( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.num );
		c.num = num.multiply( b.den );
		c.simplify();
		return c;
	}
	void print(){
		System.out.println( num + "/" + den );
	}
}


public class Solution{
	static public void main( String argv[] ) throws IOException{
		Scanner scanner = new Scanner( System.in );
		int n = scanner.nextInt();
		// calc Cnk 
		Fraction C[][] = new Fraction[n+1][n+1];
		for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) C[i][j] = new Fraction(0);
		for(int i = 0; i <= n; ++i) C[i][0] = new Fraction(1);
	
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j<= i; ++j){
				C[i][j] = C[i-1][j].add( C[i-1][j-1] );
			}
		}

		Fraction F[] = new Fraction[n+1];
		F[0] = new Fraction(1);
		BigInteger three = BigInteger.valueOf(3);
		BigInteger two = BigInteger.valueOf(2);
		for(int i = 1; i <= n; ++i){
			Fraction sum = new Fraction(1);
			Fraction div = new Fraction(BigInteger.ONE.shiftLeft(i).multiply(three).subtract(two) );
			for(int j = 0; j < i; ++j){
				sum = sum.add( F[j].multiply( C[i][j] ) );
			}
			F[i] = sum.divide(div);
		}
		F[n].print();
	}
}