TC2014_1C_950

import java.math.BigInteger;

public class RedPaint {
    static BigInteger[]fib;
    static long counter = 0L;
    private static BigInteger factorial(int n) {
        BigInteger val = BigInteger.valueOf(1L);
        for (int i = 2; i <= n ; i++) {
            val = val.multiply(BigInteger.valueOf(i));
        }
        return val;
    }

    public double expectedCells(int N) {
        int k = N;
        N = (k % 2 == 0)?k:k+1;
        BigInteger res = factorial(N).divide(factorial(N / 2));
        BigInteger res1 = BigInteger.valueOf(0);
        if (k%2 != 0){
            res1 = factorial(N - 2).divide(factorial((N - 2) / 2));
            res1 = res1.divide(factorial((N - 2) / 2));
        }
        res = res.divide(factorial(N / 2));
        double sol = res.doubleValue() / power(2,N).doubleValue();
        double sl2 = 0.0;
        if (k % 2 != 0){
            sl2 = res1.doubleValue() / power(2,(N - 2)).doubleValue();
            sol = (k + 1)*sol + (k)*sl2;
        }
        else
        sol = sol*N + sol*( N + 1);
        return sol;
    }

    private BigInteger power(int i, int n) {
        BigInteger big = BigInteger.valueOf(1);
        BigInteger exp = BigInteger.valueOf(2);
        while (n > 0){
            if (n % 2 == 0){
                exp = exp.multiply(exp);
                n /= 2;
            }
            else {
                n -=1;
                big = big.multiply(exp);
            }
        }
        return big;
    }
}