p02840 AtCoder Beginner Contest 147 - Sum Difference
We have an integer sequence A of length N, where A_1 = X, A_{i+1} = A_i + D (1 \leq i < N ) holds.

Takahashi will take some (possibly all or none) of the elements in this sequence, and Aoki will take all of the others.

Let S and T be the sum of the numbers taken by Takahashi and Aoki, respectively. How many possible values of S - T are there?

Constraints

* -10^8 \leq X, D \leq 10^8
* 1 \leq N \leq 2 \times 10^5
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N X D


Output

Print the number of possible values of S - T.

Examples

Input

3 4 2


Output

8


Input

2 3 -3


Output

2


Input

100 14 20


Output

49805
```python
N,X,D=map(int,input().split())

from collections import defaultdict

A=defaultdict(list)

A[0].append([0,0])

MIN=0
MAX=0

if D==0:
    w=1
else:
    w=D

for i in range(N):
    MIN+=X+D*i
    MAX+=X+D*(N-1-i)

    A[MIN%w].append(sorted([MIN,MAX]))

D=abs(D)
if D==0:
    if X==0:
        D=1
    else:
        D=X
ANS=0

for mod in A:
    B=A[mod]
    B.sort()
    C=[]

    for MIN,MAX in B:
        
        if C==[]:
            C.append((MIN,MAX))
        x,y=C[-1]

        if y>=MIN:
            C[-1]=(x,max(y,MAX))
        else:
            C.append((MIN,MAX))

    for MIN,MAX in C:
        ANS+=(MAX-MIN)//D+1
    
print(ANS)

```