/* Check cf5-opt.vim defs.
VIM: let g:lcppflags="-std=c++11 -O2 -pthread"
VIM: let g:wcppflags="/O2 /EHsc /DWIN32"
VIM: let g:cppflags=g:Iboost.g:Itbb
VIM: let g:ldflags=g:Lboost.g:Ltbb.g:tbbmalloc.g:tbbmproxy
VIM: let g:ldlibpath=g:Bboost.g:Btbb
VIM: let g:argv=""
*/

#include <iostream>
#include <sstream>
#include <iomanip>
#include <exception>
#include <stdexcept>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <string>
#include <memory>
#include <functional>
#include <algorithm>
#include <utility>
#include <limits>
#include <math.h>


typedef long long ll;
typedef std::vector<ll> vec;
void check( bool b ) { 	if ( !b ) 
	std::cerr << "error" << std::endl; }
#define FOR(i,l) for ( ll i =0, ie = ll(l); i<ie; ++i )

/*
	my assert
*/
void check( bool b )
{
	if ( !b )
		std::cerr << "error" << std::endl;
}

/*
	Read n values into v
*/
template <class V>
void readv( V& v, int n )
{
	v.reserve(n);
	for ( int i = 0; i < n; ++i )
	{
		typename V::value_type e;
		std::cin >> e;
		check( !std::cin.fail() );
		v.push_back(e);
	}
}

/*
	Combinations.
	Binomial coefficient.
*/
double comb(int n, int m)
{
	double r = 1;
	if ( n-m > m )
		m = n-m;
	for ( int i = n; i > m; --i )
		r *= double(i)/double(i-m);
	return r;
}

/*
	Binary probability of m ones from n possible.
*/
double prob( int n, int m )
{
	if ( n < m )
		return 0;

	double p = 1.;
	for ( int i = m; i < n ; ++i )
		p+= comb(n,i);

	return p/pow(2,n);
}

/*
	Generate and apply all permutations.
*/
template <class V, class F>
void perm( V& v, F f, size_t idx = 0 )
{
	if ( idx == v.size()-1 )
		return f(v);

	for( size_t i = idx; i < v.size(); i++ )
	{
		std::swap(v[idx],v[i]);
		perm<V,F&>(v,f,idx+1);
		std::swap(v[idx],v[i]);
	}
}