RUN Sequence is a sequence of length $N$ defined by following rules: $1 \le a_1 \le R$, $1 \le a_2 \le U$, and $a_i = a_{i-1} + a_{i-2}$ for $i \ge 3$. Jeonghyeon, the vice president of RUN, wants to find out all possible values $a_N$ as the value of $a_1$ and $a_2$ vary. Help Jeonghyeon determine the number of distinct values of $a_N$.

Constraints

• $1 \le R,U \le 10^9$
• $3 \le N \le 10^9$

Subtasks

1. (20 points) $R,U \le 1,000$; $N \le 10$

2. (30 points) $R,U \le 1,000$

3. (50 points) No additional Constraints

Input format

The first line contains three integers $R$, $U$, and $N$ separated by spaces.

Output format

Output a single integer denoting the number of distinct possible values of $a_N$.

Examples

Example 1

Input

2 3 3

Output

4

There are 4 possible values for $a_N$: 2, 3, 4, and 5.

Example 2

Input

7 9 4

Output

23