/**
*	Problem 2.1 CES 512 - D. Bozarth - 14 March 2005
*
*/

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

/**
 * Calculate the number of ways to tile an "L-shaped" region
 * whose "arms" have width 1 and length n (including vertex),
 * using all combinations of tiles of dimensions 1x1, 1x2, and 2x1.
 */
public class Ex_2_1 {

	/**
	* Constructor
	* Perform the calculation.
	*
	* @param	n	the length of each "arm"
	*/
	public Ex_2_1(int n) {
		this.nn = n;
		this.result = h(n);		
	}
	
	/**
	* Member data
	*/
	public int nn;
	public BigInteger result;

	
	/**
	* Contains a pair of BigIntegers.
	*/
	public class Pair {
		public Pair() {
			this.lo = BigInteger.ZERO;
			this.hi = BigInteger.ZERO;
		}
		public Pair(Pair inPair) {
			this.lo = inPair.lo;
			this.hi = inPair.hi;
		}
		BigInteger lo;
		BigInteger hi;
		
	}

	
	/**
	* Implement the calculation of number of combinations of tiles.
	* Running time is Big-O(n).
	*
	* @param	n	the length of each "arm"
 	* @return		the number of combinations of tiles
	*/
	public BigInteger h(int n) {
		if (n < 1) return BigInteger.ZERO;
		
		Pair pair = new Pair( g(n - 1) );
		BigInteger c = new BigInteger("0");
		c = pair.hi;
		c = c.pow(2);
		pair.hi = pair.hi.multiply(pair.lo);
		pair.hi = pair.hi.multiply( new BigInteger("2") );
		c = c.add(pair.hi);
		
		return c;
		
	}
	

	/**
	* Determine a Fibonacci number and its predecessor.
	* Accepts integer input, returns Pair of BigIntegers.
	* Running time is Big-O(n).
	*
	* @param	n	Index of the Fibonacci number
	* @return		Pair( f(n), f(n-1) )
	*/ 
	public Pair g(int n) {
		Pair pair = new Pair();
		if (n < 0) return pair;
		pair.hi = BigInteger.ONE;
		if (n == 0) return pair;
		pair.lo = BigInteger.ONE;
		if (n == 1) return pair;
		
		BigInteger c = new BigInteger("0");
		for (int i = 2; i <= n; ++i) {
			c = pair.lo;
			c = c.add(pair.hi);
			pair.lo = pair.hi;
			pair.hi = c;
		}
		
		return pair;
	
	}


	/** 
	* Find the factorial of a number.
	* Returns a BigInteger.
	*
	* @param	n	any integer
	* @return		0, if n < 0; else the factorial
	*/
	public static BigInteger fac(int n) {
		BigInteger c = new BigInteger("0");
		if (n < 0) return c;
		if (n < 2) return c.add(BigInteger.ONE);
		c = BigInteger.valueOf( (long) n );
		return c.multiply( fac(n - 1) );
		
	}


	/**
	* Estimate the number of digits in h(nBig)
	* (Based on empirical results for small values of nBig)
	* Accepts BigInteger input, returns a BigInteger.
	*
	* @param	nBig	any BigInteger
	* @return			estimated number of digits in h(nBig)
	*/
	public static BigInteger getNumberDigitsInH_Fac(BigInteger nBig) {
		if (nBig.compareTo(BigInteger.ZERO) < 0) {
			return BigInteger.ZERO;
		}
		
		BigInteger current = new BigInteger("3");
		
		if (nBig.compareTo(current) < 0) {
			return BigInteger.ONE;
		}
		if (nBig.compareTo(current) == 0) {
			return current;
		}
		
		BigInteger four = new BigInteger("4");
		BigInteger index = four;
		
		for ( ; index.compareTo(nBig) <= 0 
			  ; index = index.add(BigInteger.ONE)
			) {
			current = current.multiply(index);
			
			if ( (index.compareTo(four) == 0) 
			||   (index.compareTo( new BigInteger("9") ) == 0) ) {
				current = current.subtract( new BigInteger("2") );
			}
			if (index.compareTo( new BigInteger("6") ) == 0) {
				current = current.add(BigInteger.ONE);
			}
			if (index.compareTo( new BigInteger("8") ) == 0) {
				current = current.subtract( new BigInteger("3") );
			}
				
		}
		
		return current;	
		
	}
	
	
	/**
	* Main routine
	*
	* Receive an integer input "n" with some user choices, and either:
	*	find H(n), OR
	*	estimate the number of digits in H(n!).
	* Send output to the screen and to a file.
	*/
	public static void main(String args[]) throws IOException {
		String outFile = "outfile.txt";
		PrintWriter pw = null;
		File file = new File(outFile);
		BufferedReader kb 
			= new BufferedReader( new InputStreamReader(System.in) );

		// settings --------------------------------------------
		boolean loop = true;	// loop from zero up to myNum ?
		boolean show = false;	// show result from each loop pass ?
		boolean big  = false;	// use H(BigInteger) on a factorial ?
		boolean fact = false;	// show the factorial input to H ?
		
		// user input ------------------------------------------
		System.out.println();
		System.out.print("Enter an integer n: ");
		System.out.flush();
		int myNum = Integer.parseInt(kb.readLine());
		
		System.out.println();
		System.out.print( 
			"For H(n) enter 0. " +
			"For estimated number of digits in H(n!) enter 1: ");
		System.out.flush();
		int myBig = Integer.parseInt(kb.readLine());
		if (myBig != 0) {
			loop = true;
			big  = true;
		}
		else {
			big = false;
		}
		
		System.out.println();
		System.out.print( 
			"For single value answer, enter 0. " +
			"To loop from 0 up to n, enter 1: ");
		System.out.flush();
		int myLoop = Integer.parseInt(kb.readLine());
		if (myLoop != 0 ) {
			if (big == true) {
				show = true;
			}
			else {
				loop = true;
			}
		}
		else {
			// (myLoop == 0)
			if (big == true) {
				show = false;
			}
			else {
				loop = false;
			}
		}
		System.out.println();
		
		// computation & output---------------------------------	
		try {
			pw = new PrintWriter( new FileOutputStream(outFile), true );
		    BigInteger iBig = new BigInteger("-1");
		    
			for (int i = 0; i <= myNum; ++i) {
				if (loop == false) {
					i = myNum;
				}
				
				if (big == true  && show == true
				||  big == false && loop == true) {
					if (i != 0) {
						System.out.println();
						pw.println();
					}
					
					// Display the input number
					System.out.print(i + "   ");
					pw.print(i + "   ");
				}
						
				// Find the number of combinations
				if (big) {
					BigInteger iFac = new BigInteger("0");
					iFac = fac(i);

					if (fact == true) {
						System.out.println( iFac.toString() );
						pw.println( iFac.toString() );
					}

					iBig = iBig.add(BigInteger.ONE);

					if (show == true) {
						BigInteger iDig = getNumberDigitsInH_Fac(iBig);
						String string = new String( iDig.toString() );						
						System.out.println(string);
						pw.println(string);
					}
					
				} 
				else {
					Ex_2_1 here  = new Ex_2_1(i);
					String string = new String( here.result.toString() );
					System.out.println(string);
					pw.println(string);
				}
		
			}
			
			if (big == true && show == false) {
				BigInteger iDig = getNumberDigitsInH_Fac(iBig);
				String string = new String( iDig.toString() );						
				System.out.println(string);
				pw.println(string);
			}
		
		} 
		catch (IOException ex) {
			System.out.println( ex.getMessage() );
		
		}
		finally {
			if (pw != null) {
				pw.close();
				
			}
		
		}		
		
	}
	
}