# CFR 696 C. PLEASE ( Math )

Problem - 696C - Codeforces

The first line of input contains a single integer k (1 ≤ k ≤ 1e5) — the number of elements in array Barney gave you.
The second line contains k integers a1, a2, ..., ak (1 ≤ ai ≤ 1e18) — the elements of the array.
TL: 1000 ms
ML: 256 MB

dp[ i ]：i 回合後寶物在中間的機率
dp[ 0 ] = 1, dp[ 1 ] = 0, dp[ 2 ] = 0.5,
dp[ i ] = ( 1 - dp[ i - 1 ] ) * 0.5
dp[ i ] = -0.5 * dp[ i -1 ] + 0.5
ー> 解特徵方程式
x = -0.5 * x + 0.5, x = 1/3
dp[ i ] - 1/3 = -0.5 * ( dp[ i - 1 ] - 1/3 )
dp[ i ] = ( -0.5 )^i * ( dp[ 0 ] - 1/3 ) + 1/3
________= ( -1/2 )^i * ( 2/3 ) + 1/3
________= 1/3 * ( 1 + ( -1 )^i / 2^( i - 1 ) ) = p / q
ー> p = inverse( 3 ) * ( 2^( i - 1 ) + ( -1 )^i )
__ q = 2^( i - 1 )

O( K * lg( A ) )

```int K;
vl A;

void init(){
cin >> K;
A = vl( K );
for( int i = 0; i < K; ++i ){
cin >> A[ i ];
}
}

int int_pow( int v, ll p ){
int res = 1;
while( p ){
if( p & 1LL ){
res = 1LL * res * v % MOD7;
}
p >>= 1;
v = 1LL * v * v % MOD7;
}
return res;
}

int inv( int v ){
return int_pow( v, MOD7 - 2 );
}

void solve(){
int odd = 1;
int q = 2;
for( int i = 0; i < K; ++i ){
if( ~A[ i ] & 1LL ){
odd = 0;
}
q = int_pow( q, A[ i ] ) % MOD7;
}
q = 1LL * q * inv( 2 ) % MOD7;
int p = ( ( odd ? -1LL : 1LL ) + q ) * inv( 3 ) % MOD7;
if( p < 0 ) p += MOD7;
cout << p << "/" << q << endl;
}
```