Non-negative Solutions of a Linear Diophantine Equation

Consider the linear Diophantine equation in two variables: [ a x + b y = c ] where (a), (b), and (c) are given positive integers. Your task is to count the number of pairs ((x,y)) of non-negative integers (i.e. (x \ge 0) and (y \ge 0)) that satisfy the equation.

A necessary condition for the existence of any solution is that (\gcd(a,b)) divides (c). If this is not the case, the answer is 0.

If solutions exist, one can find a particular solution ((x_0, y_0)) using the Extended Euclidean Algorithm. The general solution is then given by: [ x = x_0 + \frac{b}{d} t, \quad y = y_0 - \frac{a}{d} t, \quad \text{with } d = \gcd(a,b) \text{ and } t \in \mathbb{Z}. ]

You need to determine all integers (t) such that (x \ge 0) and (y \ge 0), and count the total number of solutions.

inputFormat

The input consists of a single line containing three space-separated positive integers (a), (b), and (c).

outputFormat

Output a single integer: the number of non-negative integer pairs ((x,y)) that satisfy the equation (ax+by=c).

sample

3 5 8

1