Secret of the Sequence (Easy)

Time limit1sMemory limit1024 MB

Summary

Given n, p, q, r, s, and a_1, the task is to compute the sum of the first n terms of a sequence defined by a_(2i) = p*a_i + q and a_(2i+1) = r*a_i + s.

Level: Easy2 of 10
Topics: Array, Simulation
Solved: No attempts yet

Problem

A sequence $a\_1, a\_2, a\_3, \ldots, a\_n$ of length $n$ satisfies the following conditions.

$a\_{2i} = p \cdot a\_i + q$ $(2 \leq 2i \leq n)$
$a\_{2i+1} = r \cdot a\_{i} + s$ $(3 \leq 2i+1 \leq n)$

Let $S\_n = a\_1 + a\_2 + \ldots + a\_{n}$ . Print $S\_n$ .

Input

The first line contains $n$ .

The second line contains positive integers $p,q,r,s$ , separated by spaces.

The third line contains the positive integer $a\_1$ .

Output

Print the value of $S\_n$ on the first line.

Constraints

$1\leq n\leq 20$
$1\leq p,q,r,s\leq 10$
$1\leq a\_1\leq 100$

Examples2

Example 1
Input
```
3
2 1 1 2
1
```
Expected output
```
7
```
Example 2
Input
```
4
10 10 10 10
100
```
Expected output
```
12230
```