J - 2つのカップ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

水が A リットル入るカップと、水が B リットル入るカップが 1 つずつあります。

カップが空の状態から始めて、次のいずれかの操作を繰り返し行うことにより、いずれかのカップに水が C リットルたまる状態にしたいです。

  • 一方のカップを水でいっぱいにする。
  • 一方のカップを空にする。
  • 一方のカップ X からもう一方のカップ Y に、 Y がいっぱいになるか X が空になるまで、水をこぼさずにうつす。

A, B, K が与えられるので、 K 回以内の操作で実現できる相異なる C は何通りあるかを求めなさい。


入力

入力は以下の形式で標準入力から与えられる.

A B K
  • 1 行目には,カップの容量を表す整数 A,B (1 ≦ A, B ≦ 10^{10}) と、操作可能な回数を表す整数 K (0 ≦ K ≦ 10^{10}) が与えられる。

出力

実現できる相異なる C は何通りあるかを求めよ。出力の最後には改行を入れること。


入力例1

3 4 2

出力例1

4

まず、 0 は初期状態で実現されています。

3 および 4 は、それぞれの容量のカップの水を満たす、 1 回の操作で達成可能です。

1 は、 容量 4 のカップに入れた水を、空になっている容量 3 のカップに移す、2 回の操作で実現できます。

2 は、2 回の操作で実現することは出来ず、 4 回の操作が必要となります。


入力例2

7 3 0

出力例2

1

操作不可能なので、空の状態、つまり 0 のみを実現することしかできません。


入力例3

174324 96581 5000

出力例3

3220