Problem H

Integer Sequences from Addition of Terms

We consider sequences formed from the addition of terms of a given sequence. Let $\{a_n\}$, $n = 1,2,3,\ldots$, be an arbitrary sequence of integer numbers; $d$ a positive integer. We construct another sequence $\{b_m\}$, $m = 1,2,3,\ldots$, by defining $b_m$ as consisting of $n \times d$ occurrences of the term $a_n$:

$$b_1 = \underbrace{a_1, \ldots, a_1}_{d \text{ occurrences of } a_... ...underbrace{a_3, \ldots, a_3}_{3d \text{ occurrences of } a_3} \, , \quad \cdots$$

For example, if $a_n = n$, and $d = 1$, then the resulting sequence $\{b_m\}$ is:

$$\underbrace{1}_{b_1},\underbrace{2,2}_{b_2},\underbrace{3,3,3}_{b_3}, \underbrace{4,4,4,4}_{b_4},\cdots$$

Problem

Given $a_n$ and $d$ we want to obtain the corresponding $k$th integer in the sequence $\{b_m\}$. For example, with $a_n = n$ and $d = 1$ we have 3 for $k = 6$; we have 4 for $k=7$. With $a_n = n$ and $d = 2$, we have 2 for $k = 6$; we have 3 for $k=7$.

Input

The input consists of three lines:

1. The first line represents $a_n$ - a polynomial in $n$ of degree $i$ with non-negative integer coefficients in increasing order of the power:
   $$a_n = c_0+c_1 n +c_2 n^2+c_3 n^3+\cdots + c_i n^i \, ,$$
   where $c_j \in \mathbb{N}_0$, $j = 0,\ldots,i$. This polynomial $a_n$ is codified by its degree $i$ followed by the coefficients $c_j$, $j = 0,\ldots,i$. All the numbers are separated by a single space.
2. The second line is the positive integer $d$.
3. The third line is the positive integer $k$.

It is assumed that the polynomial $a_n$ is a polynomial of degree less or equal than 20 ( $1 \le i \le 20$) with non-negative integer coefficients less or equal than 10000 ( $0 \le c_j \le 10000$, $j = 0,\ldots,i$); $1 \le d \le 100000$; $1 \le k \le 1000000$.

Output

The output is the $k$th integer in the sequence $\{b_m\}$. This value is less or equal than $2^{63}-1$.

Sample Input

4 3 0 0 0 23
25
100

Sample Output

1866

MIUP’2004: Fourth Portuguese National Programming Contest