Description

A train departs from the origin (called station $1$). At the origin, $a$ people board. It then arrives at station $2$; at station $2$ some people board and alight, but the numbers boarding and alighting are equal, so when departing station $2$ (i.e., before arriving at station $3$), there remain $a$ people on the train. From station $3$ onward (including station $3$), the numbers boarding and alighting follow a rule: the number boarding at each station equals the sum of the numbers who boarded at the previous two stations, and the number alighting equals the number who boarded at the previous station. This holds through the penultimate station, station $n-1$. You are given that there are $n$ stations in total, $a$ people board at the origin, and at the last station the number of people alighting is $m$ (everyone gets off). Find the number of people on the train when departing station $x$.

Input Format

A single line containing four integers: the number of people boarding at the origin $a$, the number of stations $n$, the number of people alighting at the terminal station $m$, and the station index to query $x$.

Output Format

Output a single integer: the number of people on the train when departing station $x$.

5 7 32 4

13

Hint

For all test cases, $1 \leq a \leq 20$, $1 \leq x \leq n \leq 20$, $1 \leq m \leq 2 \times 10^4$.

NOIP 1998 Senior Problem 1.

Translated by ChatGPT 5