import java.math.BigDecimal;
import java.math.BigInteger;


public class Flipper {

	static BigInteger kStepFib( int k, int n )
	{
		int arraySize = n + 1;
		if ( arraySize < 3 )
			arraySize = 3;
		BigInteger fibs[] = new BigInteger[ arraySize ];
		fibs[ 0 ] = new BigInteger( "0" );
		fibs[ 1 ] = new BigInteger( "1" );
		fibs[ 2 ] = new BigInteger( "1" );
		for ( int i = 3 ; i <= n ; i++ ) {
			BigInteger fib = new BigInteger( "0" );
			int start = i - k;
			for ( int j = i - k ; j < i ; j++ )
				if ( j > 0 )
					fib = fib.add( fibs[ j ] );
			fibs[ i ] = fib;
			if ( start >= 0 )
				fibs[ start ] = null;
			if (( i % 1000)  == 0 )
					System.out.print( "i= " + i + "\r" );
		}
		return fibs[ n ];
	}
	public static void main(String[] args) {
		final int k = 20;
		final int n = 1000000;
		final int showdigits = 100;
		BigDecimal f = new BigDecimal( kStepFib( k, n + 2) );
		BigDecimal p = new BigDecimal( (new BigInteger( "2" )).pow( n ) );
		String fs = f.toString();
		System.out.println( "\nfib(" + k + "," + (n+2) + ") = " + fs.substring(0, showdigits)  + " (" + (fs.length() - showdigits ) + " digits elided)" );
		String ps = p.toString();
		System.out.println( "2^" + n + " = " + ps.substring(0, showdigits) + " (" + (ps.length() - showdigits ) + " digits elided)" );
		BigDecimal answer = f.divide(p);
		answer = (new BigDecimal(1)).subtract(answer);
		String s = answer.toString();
		System.out.println( "Div = " + s.substring(0, showdigits ) + " (" + (s.length() - showdigits ) + " digits elided)" );
		
	}

}