Fibonacci sequence#3147
Sign in

Fibonacci sequence

1 second
64 megabytes
Hard

A sequence of numbers a_1, a_2, \ldots is called a Fibonacci sequence if for any i \geq 3, the following holds:

a_i = a_{i-1} + a_{i-2}.

You are given two elements of this sequence with indices and . Find the -th element of the sequence.

In the second example, the Fibonacci sequence is , , , , , ,

Input

You are given the numbers , , , a_i, a_j. Constraints: , , are natural numbers not exceeding 10^6, and are always distinct; a_i and a_j are integers whose absolute values do not exceed 2 \cdot 10^9.

Output

Output a_k. The input is such that all members of the sequence are integers, and a_k does not exceed 2 \cdot 10^9 in absolute value.

Examples

Example 1

Loading
Loading