RUN Sequence는 $1 \le a_1 \le R$, $1 \le a_2 \le U$이고, $i \ge 3$인 $i$에 대해서 $a_i = a_{i-1} + a_{i-2}$으로 정의되는 길이 $N$의 수열이다. RUN의 부회장인 정현이는 $a_1, a_2$의 값이 바뀜에 따라 $a_N$으로 가능한 값들이 무엇이 있는지 조사하고자 한다. 정현이에게 $a_N$으로 가능한 값의 개수를 알려 주자.

제약 조건

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

부분문제

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

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

3. (50점) 추가 제약 조건 없음.

입력 형식

첫째 줄에 세 정수 $R$, $U$, $N$이 공백으로 구분되어 주어진다.

출력 형식

$a_N$으로 가능한 서로 다른 값의 개수를 출력한다.

예제

예제 1

입력

2 3 3

출력

4

$a_N$의 값으로 가능한 수는 $2$, $3$, $4$, $5$로, 4가지이다.

예제 2

입력

7 9 4

출력

23