Polynomial

Time limit1sMemory limit128 MB

Summary

Given a degree-n polynomial's values at 0 through n, compute its value at n+1.

Level: Medium6 of 10
Topics: Math, Prefix sum, Implementation
Solved: No attempts yet

Problem

A polynomial $W$ of degree at most $n$ is given by its values at the points $0, 1, 2, \dots, n$ . Your task is to determine the value of this polynomial at the point $n+1$ .

Write a program that:

reads the (maximum) degree $n$ of the polynomial and its values at the points $0, 1, \dots, n$ ,
computes the value of the polynomial at the point $n+1$ ,
prints the result.

Input

The first line contains one positive integer $n$ , the (maximum) degree of the polynomial, with $1 \le n \le 10000$ . Each of the next $n+1$ lines contains one integer: the values $w(0), w(1), \dots, w(n)$ of the polynomial at the successive points, where $-10^9 < w(i) < 10^9$ . For every input the requested result is an integer.

Output

Print a single integer: the value of the polynomial at the point $n+1$ .

Examples1

Example 1
Input
```
4
7
6
9
16
27
```
Expected output
```
42
```