問題文

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

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

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

A, B, K が与えられるので、 K 回以内の操作で実現できる相異なる 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