Number of People on the Train

Problem Background

Special for beginners, ^_^

Problem Description

A train departs from the starting station (called station $1$) with $a$ people boarding at station $1$. It then arrives at station $2$, where some people board and some alight, but the number boarding equals the number alighting, so when the train leaves station $2$ (i.e. before arriving at station $3$) the number of people on board remains $a$.

From station $3$ onward (including station $3$), the boarding and alighting follow a pattern: the number boarding at each station equals the sum of the numbers that boarded at the previous two stations, and the number alighting equals the number that boarded at the previous station. This holds up to the station before the terminal (station $n - 1$).

The given conditions are: there are $n$ stations in total, $a$ people board at the starting station, and $m$ people alight at the last station (everyone gets off). The question is: how many people are on the train when it leaves station $x$?

Input Format

One line containing four integers $a$, $n$, $m$, and $x$, separated by single spaces. $0 \le a \le 10$, $3 \le x < n \le 15$, $0 \le m \le 10000$.

The data is guaranteed to have a unique solution. People may board and alight at the same station.

Output Format

One integer: the number of people on the train when it leaves station $x$.

Sample Input

5 7 32 4

Sample Output

13

Hint

Assume the number of people boarding at station $2$ is $k$.

Constraints

1s, 1024KiB for each test case.