# hdu 5481||bestcoder #57 div 2 C Desiderium (概率)

2015年9月30日 作者 CrazyKK

# Desiderium

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 427    Accepted Submission(s): 167

Problem Description

There is a set of intervals, the size of this set is

If we select a subset of this set with equal probability, how many the expected length of intervals’ union of this subset is?

We assume that the length of empty set’s union is 0, and we want the answer multiply

Input

The first line of the input is a integer

Every test cases begin with a integer

Then

Output
For every test case output the answer multiply

Sample Input
2
1
0 1
2
0 2
1 3

Sample Output

1 7

Hint

For the second sample, the excepted length is $frac{0+2+2+3}{4}=frac{7}{4}$.

1、空集，集合中区间的并的长度为0

2、{区间1}，集合中区间的并的长度为2

3、{区间2}，集合中区间的并的长度为2

4、{区间1、区间2}，集合中区间的并为[0,3]，长度为3

…………